Expand knowledge base

1 files changed, 234 insertions, 0 deletions

diff --git a/content/know/concept/bb84-protocol/index.pdc b/content/know/concept/bb84-protocol/index.pdc
new file mode 100644
index 0000000..9f7c7db
--- /dev/null
+++ b/content/know/concept/bb84-protocol/index.pdc
@@ -0,0 +1,234 @@
+---
+title: "BB84 protocol"
+firstLetter: "B"
+publishDate: 2021-03-06
+categories:
+- Quantum information
+- Cryptography
+
+date: 2021-03-06T09:44:16+01:00
+draft: false
+markup: pandoc
+---
+
+# BB84 protocol
+
+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}
+    | \braket{0}{+} |^2 = | \braket{0}{-} |^2 = | \braket{1}{+} |^2 = | \braket{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.