| Category: QKD |
At this point, Alice and Bob posses identical strings, but those strings are not completely private. Eve may have gained some information about them either by beamsplitting or through intercept/resend. Although this second strategy may cause some errors in Bob's string, if Eve uses it on only a small number of bits, the induced errors will be lost among the errors caused by noise in the detectors and other physical problems. During the reconciliation phase, Eve did not gain any information, since the last bit of each parity check set was discarded. However, some of her original information about specific bits may have been converted to information about parity bits. For instance, if she knew the value of a bit x in string y, and Alice and Bob revealed the parity of y and discarded x, Eve would then know the parity of the remaining bits of y. If we say that Eve knows a parity bit about a string if she knows the parity of a non-empty subset of that string, then if Eve started out knowing at most k physical bits of the key, she will know at most k parity bits of the key after reconciliation [1].
In any case, Alice and Bob share an n-bit string S, and we will suppose that Eve knows at most k deterministic (i.e. parity or physical) bits of S. Alice and Bob wish to compute an r-bit key K, where r < n, such that Eve's expected information about K is below some specified bound. To do so, they will choose a compression function g: {0,1}n -> {0,1}r and compute K = g(S). The question is, what kinds of functions are appropriate for this purpose? That is, which functions, when applied to S, will yield a K about which Eve knows almost nothing?
Definition: [2] A class G of functions A -> B is universal2 if for any distinct x1 and x2 in A, the probability that g(x1) = g(x2) is at most 1/|B| when g is chosen at random from G according to the uniform distribution.
An example of a universal class is the set of permutations of A onto itself, since for any g in the set, the probability that g(x1) = g(x2) is zero, which is less than 1/|A|. It is shown in [2] that if Eve knows k deterministic bits of S, and Alice and Bob choose their compression function g at random from a universal class of hash functions {0,1}n -> {0,1}r where r = n - k - s for some safety parameter 0 < s < n-k, then Eve's expected information about K = g (S) is less than or equal to 2-s/ln2 bits. One such hash function to generate K [1] is for Alice and Bob to compute an additional r random subset parities of S, this time keeping the results secret. The r results of the parities will be the final r-bit key.
Given this result, one might ask how Alice and Bob are to determine the value of k, i.e. how much information has been leaked to Eve. As a conservative estimate, they can simply assume that all transmission errors were caused by eavesdropping (although most likely some came from detection errors). Eavesdropping errors could come from either intercept/resend or beamsplitting. Alice and Bob can use the beam intensity m and the bit error rate to calculate the expected fraction of S that Eve has learned. If they are conservative in their assumptions and add several standard deviations to their results, they will have a safe upper bound on the number of bits leaked to Eve. (See [1] for more details.)
The above discussion assumes that Eve knows only deterministic bits, so another issue is whether it might be more useful to her to obtain probabilistic information about S instead. In other words, rather than measuring photons in the same bases as Alice and Bob, she could pick a basis halfway in between them. This will give her a result that matches Alice's with probability approximately 85%, regardless of which basis Alice uses [3]. She will not gain any information when Bob reveals his measurement choices, so with this strategy all of her information is probabilistic rather than deterministic. Conceivably, this probabilistic information could be more resistant to privacy amplification than deterministic information. However, it turns out that this is not the case [3], so if Eve wishes to optimize her expected information on the final key, she should use the same bases as Alice and Bob, obtaining only deterministic bits.