The protocol works because it uses a set of quantum states that cannot be fully distinguished from each other. Still, you may ask why would this be enough? If we run the protocol, how do we know that the keys the Alice and Bob get are indeed identical and private?
This means we must show that Alice's key is the same as Bob's key, and that any outside party, say Eve, cannot have too much knowledge about either key. That is exactly what we would need to do to prove the security of a quantum key distribution (QKD) protocol.
We say that a QKD protocol is secure if it produces a correct and secret key. A key is correct if Alice and Bob obtain precisely the same bit string. A key is secret if given a set of $N$ possible keys, the probability that Alice and Bob get any particular key is $\frac{1}{N}$. In other words, the key is uniformly distributed.
 |
| A standard QKD protocol involves a quantum channel where Alice can send quantum states to Bob, and a classical channel where they can discuss publicly. An eavesdropper Eve has access to both channels but she cannot alter messages in the classical channel. The output of the protocol is a pair of random strings called keys, one each for Alice and Bob. The protocol is secure if (i) Alice and Bob obtain the same key and (ii) the key is uniformly distributed. |
It is easy to understand the correctness of a key since obviously Alice and Bob cannot share a key if they have different bit strings. It maybe a bit less clear why the secrecy of the key depends on the probability distribution of the set of possible keys.
Roughly speaking, if some of the bit strings are more likely than others, this tells Eve something about the key. This can be seen by considering a somewhat extreme case. Suppose a certain QKD protocol generates a 2-bit key $k$ such that
$\Pr[k = 00] = \Pr[k = 01] = 0.45, \quad \Pr[k =10] = \Pr[k = 11] = 0.05.$
In this case, Eve can just conclude that the first bit of the key is probably 0, and she has a 90% chance of being right. In some sense, this describes how Eve tries to learn about the key: she attacks the protocol so it produces key that is much less uniformly distributed.
We see that the worst case for Eve is when even after her attack, all the possible keys are equally likely. Here the best she can do is guess purely at random. So now it should be clear why a uniformly random key implies a secret key.
Of course, in practice we can slightly relax our security demands. We might allow a small chance that Alice and Bob do not get the same key, or we might be satisfied with a key that is nearly uniformly distributed. As long as the probability of obtaining a correct and secret key is very high, that is certainly good enough.
How to achieve a correct key
In the BB84 protocol, when Eve is absent then Alice and Bob can generate a secure key from those qubits that Alice sent and Bob measured in the same basis. If Eve attempts to identify the states sent by Alice to Bob, she inevitably introduces errors by making Alice and Bob's keys not match. Alice and Bob can find this out if they use some of their data to check that their keys are the same.
Note that if the quantum channel is noisy, it also can create errors in the key. So how do we actually get a correct and secret key in the presence of noise, whether due to Eve or to imperfections in the channel? What we can show is that if the noise is low enough, then it is possible to correct the errors and reduce Eve's knowledge about the key. In BB84, once Alice and Bob determine which bits were obtained from the same basis, then Alice and Bob will each have a sifted key.
The first step is to perform error correction on the sifted keys over the public classical channel, which is called information reconciliation. The general approach is based on the idea of error-correcting codes. Here we will consider an example using the Brassard-Salvail Cascade method [1].
In Cascade, the sifted keys are split into a number of blocks and the parity of each block are compared. If a difference in parity is found, Alice and Bob perform a binary search to locate and correct the error. That is, they divide the block into two halves, compare the sub-block parities, and continue dividing until the error is found. Once they compare all blocks and correct for all mismatch parities, the round is over.
In the next round, Alice and Bob first randomly reorder their bit strings then divide them into blocks with twice the size of the previous round. They repeat the process of comparing blocks and finding errors. After four rounds, the corrected strings will be identical with high probability.
Note that each time Alice and Bob compare parities, they are essentially revealing partial information about the key to Eve. Thus, it is crucial to optimize the initial size $w$ of the blocks relative to the tolerated error rate $e$. In the original Cascade, they recommended an intial block size of $w \approx \lceil \frac{0.73}{e} \rceil$ bits.
To demonstrate Cascade, suppose Alice and Bob start with the following sifted keys:
Alice's string: 1010 0110 0100 0010
Bob's string: 1010 0100 0100 0010
In the first round, they choose a block size of 4. Computing the parities, they find that
Alice's parities: 0 0 1 1
Bob's parities: 0 1 1 1
They find a difference in the second block so they perform binary search. Splitting the second block into two halves:
Alice's 2nd block: 01 10
Bob's 2nd block: 01 00
Computing the parity of the first half of the second block:
Alice's 2nd block 1st half parity: 1
Bob's 2nd block 1st half parity: 1
The first half has same parity so the error must be in the second half. Comparing the first bits of the second half:
Alice's 2nd block, 1st bit of 2nd half: 1
Bob's 2nd block, 1st bit of 2nd half: 0
They found the mismatched bits so they can make them equal say if Bob flips his bit. There are no more blocks with different parities so the round is over. Since our example only had a single bit error, the string are already matching.
Alice's string: 1010 0110 0100 0010
Bob's string: 1010 0110 0100 0010
However, Alice and Bob would not know this so they will proceed to the second round. To begin, Alice and Bob first have to randomly rearrange their bit strings. This is necessary because if there are two errors in a block, this will not be detected by comparing block parities. So in each round we rearrange the strings in order to redistribute the errors.
In our example, suppose Alice and Bob perform the following reordering:
$(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) \mapsto (1,9,2,10,3,4,15,16,5,6,11,12,7,13,14,8)$
Afterwards, we have
Alice's string: 10011010 01001000
Bob's string: 10011010 01001000
since now the block size is 8. Again Alice and Bob should compare the block parities:
Alice's parities: 0 0
Bob's parities: 0 0
They find they are the same so no corrections are needed for this round. Since our example used only 16 bits we can stop here but normally Alice and Bob will proceed for two more rounds before halting.
How to achieve a secret key
Our example shows that for low error rate (like 1 bit error in 16 bits), we can find and correct errors to make Alice and Bob's keys identical. However, this comes at the price of revealing a number of parity bits. In the example, we had to reveal a total of 8 parity bits over two rounds. This means at least half of the key is already known by Eve.
Clearly, we need to reduce Eve's partial information, whether it was gained during eavesdropping on the quantum channel, or on the classical channel during information reconciliation. This step is known as privacy amplification. It is generally done using a universal hash function, chosen randomly from a publicly known family of such functions. It maps a bit string into a shorter string, where how much the length is reduced is based on a bound on how much Eve knows about the key.
The bound can calculated based on the expected error rate in the quantum channel and the bit revealed during information reconciliation. A precise calculation of the best bound can be quite complicated. However, there is a relative simple result we can use if we are willing to sacrifice more bits than is absolutely necessary to achieve secrecy.
Bennett, Brassard, Crépeau and Maurer derived the following theorem [2]: Suppose that for some $n$-bit string, eavesdropping reveals at most $t$ bits to Eve. Let $s < n - t$ be a security parameter and $r = n - t - s$. Then the Eve's expected information about the key can be bounded by $\frac{2^{-s}}{\ln(2)} \approx (1.443)2^{-s}$.
To see how this works, in our example above with $n=16$ suppose that Alice and Bob chose the error rate threshold to be 12.5%. This means that if all the errors are due to Eve, then Eve can potential know 2 of 16 bits after eavesdropping on the quantum channel. Since 8 parity bits were revealed, then in the worst case Eve might know $t = 10$ of the bits of the corrected keys.
Suppose we choose $s = 4$. Then $r = n - t- s = 2$. Now Alice and Bob can choose a random full-rank $r \times n$ binary matrix (all entries 0 or 1) to apply to their $n$-bit key when written as a $n \times 1$ vector. Thus, we compute each bit of the key as the parity of several bits. The idea then is if Eve knows bit $x$ but not bit $y$, then she does not know $x \oplus y$.
In our example, suppose Alice and Bob picked the matrix
$H = \begin{pmatrix}
0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1
\end{pmatrix}. $
Let $v$ be the key written as a column vector, i..e,
$v = \begin{pmatrix}
1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0
\end{pmatrix}^{T}.$
Then
$ K = Hv = \begin{pmatrix}
1 \\ 0
\end{pmatrix}.$
The theorem above tells us that on average, Eve will know $\frac{2^{-4}}{\ln(2)} \approx 0.0902$ bits of this 2-bit key.
Of course, in our example, Eve still knows a bit too much since on average she still knows roughly 4.5% of the key. But if we had a longer string where we can choose a larger $s$ we can reduce Eve's knowledge more significantly.
References:
[1] G. Brassard and L. Salvail "Secret key reconciliation by public discussion", Advances in Cryptology: Eurocrypt 93 Proc. (1993) 410-23.
[2] C. Bennett, G. Brassard, C. Crépeau, and U. M. Maurer, "Generalized privacy amplification", IEEE Trans. Inform. Tehory 41 (1995) 1915-23.
No comments:
Post a Comment