diff options
Diffstat (limited to 'source/know/concept/bb84-protocol/index.md')
| -rw-r--r-- | source/know/concept/bb84-protocol/index.md | 233 |
1 files changed, 233 insertions, 0 deletions
diff --git a/source/know/concept/bb84-protocol/index.md b/source/know/concept/bb84-protocol/index.md new file mode 100644 index 0000000..95ba720 --- /dev/null +++ b/source/know/concept/bb84-protocol/index.md @@ -0,0 +1,233 @@ +--- +title: "BB84 protocol" +date: 2021-03-06 +categories: +- Quantum information +- Cryptography +layout: "concept" +--- + +The **BB84** or **Bennett-Brassard 1984** protocol is +a *quantum key distribution* (QKD) protocol, +whose purpose is to securely transmit a string of random bits +over a quantum channel for later use as a one-time pad. +It is provably information-secure, thanks to the fact that +quantum channels cannot be eavesdropped without interfering with the signal. + +Alice wants to send a secret key to Bob. +Between them, they have one quantum channel and one classical channel. +Both channels may have eavesdroppers without compromising the security of the BB84 protocol, +as long as Alice and Bob authenticate all data sent over the classical channel. + +First, Alice securely generates a sequence of random (classical) bits. +Note that the BB84 protocol is only suitable for random (high-entropy) data, +because the later stages of the protocol involve revealing parts of the data +over the (insecure) classical channel. + +For each bit, Alice randomly chooses a qubit basis, +either $\{ \Ket{0}, \Ket{1} \}$ (eigenstates of the $z$-spin $\hat{\sigma}_z$) +or $\{ \Ket{-}, \Ket{+} \}$ (eigenstates of the $x$-spin $\hat{\sigma}_x$). +Using the basis she chose, she then transmits the bits to Bob over the quantum channel, +encoding them as follows: + +$$\begin{aligned} + 0 \:\:\rightarrow\:\: \Ket{0} \:\mathrm{or}\: \Ket{+} + \qquad \quad + 1 \:\:\rightarrow\:\: \Ket{1} \:\mathrm{or}\: \Ket{-} +\end{aligned}$$ + +Crucially, Bob has no idea which basis Alice used for any of the bits. +For every bit, he chooses $\hat{\sigma}_z$ or $\hat{\sigma}_x$ at random, +and makes a measurement of the qubit, yielding 0 or 1. +If he guessed the basis correctly, he gets the bit value intended by Alice, +but if he guessed incorrectly, he randomly gets 0 or 1 with a 50-50 probability: + +$$\begin{aligned} + | \Inprod{0}{+} |^2 = | \Inprod{0}{-} |^2 = | \Inprod{1}{+} |^2 = | \Inprod{1}{-} |^2 = \frac{1}{2} +\end{aligned}$$ + +After Alice has sent all her qubits, +the next step is **basis reconciliation**: +over the classical channel, Bob announces, for each bit, +which basis he chose, and Alice tells him if he was right or wrong. +Bob discards all bits where he guessed wrongly. +If their quantum channel did not have any noise or eavesdroppers, +Alice and Bob now have a perfectly correlated secret string of bits. + + +## Eavesdropper detection + +But what if there is actually an eavesdropper? +Consider a third party, Eve, who wants to intercept Alice' secret string. +The main advantage of using QKD compared to classical protocols +is that such an eavesdropper can be detected. + +Suppose that Eve is performing an *intercept-resend attack* +(not very effective, but simple), +where she listens on the quantum channel. +For each qubit received from Alice, Eve chooses +$\hat{\sigma}_z$ or $\hat{\sigma}_x$ at random and measures it. +She records her results and resends the qubits to Bob +using the basis she chose, which may or may not be what Alice intended. + +If Eve guesses Alice' basis correctly, her presence is not revealed, +and the protocol proceeds as normal. +However, if she guesses wrongly (which has a probability of 50%), +her bit value might be incorrect, and she will resend whatever she measured +to Bob encoded in the wrong basis. + +If we assume that Eve chose wrongly, +Bob might measure using Eve's basis, +which will yield a 50% error rate due to Eve's mistake. +Otherwise, Bob might measure using Alice' basis, +which will also yield a 50% error rate due to the disagreement with Eve. + +In the end, the probability is 0.5 that Eve chose correctly, +which, multiplied by the 0.5 error rate from Bob's choice, +will result in a 0.25 error rate due to Eve's presence. +To detect this, after basis reconciliation, +Bob reveals a part of his secret string as a sacrifice, +which allows Alice to estimate the error rate. +If the rate is too high, Eve is detected, and the protocol can be aborted, +although that is not mandatory. + +This was an intercept-resend attack. +There exist other attacks, but similar logic holds. +It has been proven by Shor and Preskill in 2000 +that as long as the error rate is below 11%, +the BB84 protocol is fully secure, i.e. there cannot be any eavesdroppers. + + +## Error correction + +In practice, even without Eve, quantum channels are imperfect, +and will introduce some errors in the qubits received by Bob. +Suppose that after basis reconciliation, +Alice and Bob have the strings +$\{a_1, ..., a_N\}$ and $\{b_1, ..., b_N\}$, respectively. +We define $p$ as the probability that Alice and Bob agree on the $n$th bit, +which we assume to be greater than 50%: + +$$\begin{aligned} + p = P(a_n = b_n) > \frac{1}{2} +\end{aligned}$$ + +Ideally, $p = 1$. To improve $p$, the following simple scheme can be used: +starting at $n = 1$, Alice and Bob reveal $A$ and $B$ over the classical channel, +where $\oplus$ is an XOR: + +$$\begin{aligned} + A = a_n \oplus a_{n+1} + \qquad \quad + B = b_n \oplus b_{n+1} +\end{aligned}$$ + +If $A = B$, then $a_{n+1}$ and $b_{n+1}$ are discarded to prevent +a listener on the classical channel from learning anything about the string. +If $A \neq B$, all of $a_n$, $b_n$, $a_{n+1}$ and $b_{n+1}$ are discarded, +and then Alice and Bob move on to $n = 3$, etc. + +Given that $A = B$, the probability that $a_n = b_n$, +which is what we want, is given by: + +$$\begin{aligned} + P(a_{n} = b_{n} | A = B) + &= \frac{P(a_{n} = b_{n} \land A = B)}{P(A = B)} + \\ + &= \frac{P(a_{n} = b_{n} \land a_{n+1} = b_{n+1})}{P(a_{n} = b_{n} \land a_{n+1} = b_{n+1}) + P(a_{n} \neq b_{n} \land a_{n+1} \neq b_{n+1})} + \\ + &= \frac{P(a_{n} = b_{n}) \: P(a_{n+1} = b_{n+1})}{P(a_{n} = b_{n}) \: P(a_{n+1} = b_{n+1}) + P(a_{n} \neq b_{n}) \: P(a_{n+1} \neq b_{n+1})} +\end{aligned}$$ + +We use the definition of $p$ to get the following inequality, +which can be verified by plotting: + +$$\begin{aligned} + P(a_{n} = b_{n} | A = B) + = \frac{p^2}{p^2 + (1 - p)^2} + > p +\end{aligned}$$ + +Alice and Bob can repeat this error correction scheme multiple times, +until their estimate of $p$ is satisfactory. +This involves discarding many bits, +so the length $N_\mathrm{new}$ of the string they end up with +after one iteration is given by: + +$$\begin{aligned} + N_\mathrm{new} + = \frac{1}{2} N_\mathrm{old} P(A = B) + = \frac{1}{2} N_\mathrm{old} \big( p^2 + (1 - p)^2 \big) +\end{aligned}$$ + +More efficient schemes exist, which do not consume so many bits. + + +## Privacy amplification + +Suppose that after the error correction step, $p = 1$, +so Alice and Bob fully agree on the random string. +However, in the meantime, Eve has been listening, +and has been doing a good job +building up her own string $\{e_1, ..., e_N\}$, +such that she knows more that 50% of the bits: + +$$\begin{aligned} + q = P(e_n = a_n) > \frac{1}{2} +\end{aligned}$$ + +**Privacy amplification** is an optional final step of the BB84 protocol +which aims to reduce Eve's $q$. +Alice and Bob use their existing strings to generate a new one +$\{a_1', ..., a_M'\}$: + +$$\begin{aligned} + a_1' + = a_1 \oplus a_2 = b_1 \oplus b_2 + \qquad + a_2' + = a_3 \oplus a_4 = b_3 \oplus b_4 + \qquad + \cdots +\end{aligned}$$ + +Note that this halves the string's length; +more efficient schemes exist, which consume less. + +To see why this improves Alice and Bob's privacy, +suppose that Eve is following along, +and creates a new string $\{e_1', ..., e_M'\}$ +where $e_m' = e_{2m - 1} \oplus e_{2m}$. +The probability that Eve's result agrees with +Alice and Bob's string is given by: + +$$\begin{aligned} + P(e_m' = a_m') + &= P(e_1 = a_1 \land e_2 = a_2) + P(e_1 \neq a_1 \land e_2 \neq a_2) + \\ + &= P(e_1 = a_1) \: P(e_2 = a_2) + P(e_1 \neq a_1) \: P(e_2 \neq a_2) +\end{aligned}$$ + +Recognizing $q$ 's definition, +we find the following inequality, +which can be verified by plotting: + +$$\begin{aligned} + P(e_m' = a_m') + = q^2 + (1 - q)^2 + < q +\end{aligned}$$ + +After repeating this step several times, $q$ will be close to 1/2, +which is the ideal value: for $q =$ 0.5, +Eve would only know 50% of the bits, +which is equivalent to her guessing at random. + + +## References +1. N. Brunner, + *Quantum information theory: lecture notes*, + 2019, unpublished. +2. J.B. Brask, + *Quantum information: lecture notes*, + 2021, unpublished. |