path: root/source/know/concept/bb84-protocol/index.md

---
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.