Simple Algorithm
Quantum Computing · Excited State · 24 min

Quantum Key Distribution: BB84 & E91

Detecting an eavesdropper by the disturbance they cannot avoid.

Every key exchange your browser performs today is secure only because certain math problems are believed to be hard, and Shor's algorithm solves the most common ones. BB84 swaps that belief for a law of physics: you cannot learn anything about non-orthogonal quantum states without disturbing them. In this lesson you run the protocol, compute exactly how loudly an eavesdropper is caught, and grow the same key from entanglement and a Bell test.

What you’ll learn

  • State the BB84 protocol (preparation, measurement, sifting, parameter estimation, error correction, privacy amplification) and the role of each step.
  • Derive the 25% error rate of the intercept-resend attack and the probability that Eve survives nn test bits.
  • Prove that, for non-orthogonal states, any information gain causes disturbance.
  • Describe E91 and its trusted-device variant BBM92, and explain how a CHSH test certifies the key.
  • Compute the asymptotic key rate 1−2h(Q)1-2h(Q) and locate the 11% error threshold.

The key-distribution problem

The one-time pad is unbreakable: to send a message mm, transmit c=m⊕kc=m\oplus k with a uniformly random key kk as long as mm, used once. Shannon (1949) proved that cc is statistically independent of mm, so no amount of computing power helps an eavesdropper. The catch is the key. Alice and Bob need a fresh, shared, secret kk for every message.

Public-key cryptography (Diffie–Hellman, RSA, elliptic curves) solves the distribution problem, but only computationally: its security rests on factoring and discrete logarithms being hard, and those are exactly the problems Shor's algorithm solves. Quantum key distribution (QKD) attacks the distribution problem with physics instead.

Think first Why must a one-time pad never be reused? Suppose Alice sends c1=m1⊕kc_1=m_1\oplus k and c2=m2⊕kc_2=m_2\oplus k.

Eve computes c1⊕c2=m1⊕m2c_1\oplus c_2=m_1\oplus m_2: the key cancels. Natural-language messages are highly redundant, so m1⊕m2m_1\oplus m_2 can usually be unravelled into both messages. (This is how the US Venona project broke Soviet messages from the 1940s whose pad pages had been reused.) Perfect secrecy needs fresh key at the rate you communicate, which is exactly what QKD tries to supply.

BB84, step by step

BB84 (Bennett & Brassard, 1984) uses two bases of a qubit, in practice a photon's polarization:

Z: {∣0⟩,∣1⟩},X: {∣+⟩,∣−⟩},∣⟨0∣±⟩∣2=∣⟨1∣±⟩∣2=12.Z:\ \{\ket0,\ket1\},\qquad X:\ \{\ket+,\ket-\},\qquad \abs{\braket{0|\pm}}^2=\abs{\braket{1|\pm}}^2=\tfrac12 .

The two bases are mutually unbiased: a state from one gives perfectly random outcomes in the other. Bit value aa is encoded as ∣a⟩\ket{a} in ZZ or as H∣a⟩H\ket{a} in XX.

  1. Preparation. For each round ii, Alice picks a random bit aia_i and a random basis θi∈{Z,X}\theta_i\in\{Z,X\}, and sends the state encoding aia_i in basis θi\theta_i.
  2. Measurement. Bob measures each arriving qubit in his own random basis θi′\theta_i', obtaining bib_i.
  3. Sifting. Over the classical channel they announce the bases, never the bits, and keep only rounds with θi=θi′\theta_i=\theta_i': about half. This is the sifted key.
  4. Parameter estimation. They publish a random sample of sifted bits and compute the quantum bit error rate (QBER) QQ. If QQ exceeds a threshold, they abort.
  5. Error correction. They reconcile the remaining bits, publicly revealing some parity information.
  6. Privacy amplification. They hash the corrected string to a shorter one, about which Eve's information is negligible.
Alice's bitAlice's basisState sentBob's basisBob's resultKept?
0ZZ∣0⟩\ket0ZZ0yes
1XX∣−⟩\ket-ZZ0 or 1 (random)no
1XX∣−⟩\ket-XX1yes
0ZZ∣0⟩\ket0XX0 or 1 (random)no
1ZZ∣1⟩\ket1ZZ1yes
Five rounds without an eavesdropper. Mismatched rounds carry no correlation and are discarded; matched rounds agree perfectly.
Check your understanding

Alice sends ∣+⟩\ket+ and Bob measures in the ZZ basis. What does Bob observe?

  1. Always 0, because ∣+⟩\ket+ encodes the bit 0
  2. 0 or 1 with probability ½ each, uncorrelated with Alice's bit
  3. Always 1, because the bases disagree
  4. Nothing: a photon measured in the wrong basis is absorbed
Show the answer

B. 0 or 1 with probability ½ each, uncorrelated with Alice's bit

∣⟨0∣+⟩∣2=∣⟨1∣+⟩∣2=12\abs{\braket{0|+}}^2=\abs{\braket{1|+}}^2=\tfrac12. The outcome is a fair coin, independent of Alice's bit, which is why sifting discards these rounds.

Eve's dilemma: information costs disturbance

Eve's simplest strategy is intercept-resend: measure each photon in a basis of her choosing and send Bob a fresh photon in the state she observed. She cannot copy the photon instead, because the no-cloning theorem forbids a copier for a set containing both ∣0⟩\ket0 and ∣+⟩\ket+.

DerivationIntercept-resend produces a 25% error rate
  1. P(Eve guesses Alice’s basis)=12P(\text{Eve guesses Alice's basis})=\tfrac12

    The bases are announced only after Bob has measured, so Eve must guess.

  2. right basis: she obtains a and resends the same state ⇒ P(error∣right)=0\text{right basis: she obtains } a \text{ and resends the same state}\ \Rightarrow\ P(\text{error}\mid\text{right})=0

    In these rounds she learns the bit and leaves no trace.

  3. wrong basis: she resends ∣e⟩θˉ,∣⟨aθ∣eθˉ⟩∣2=12 ⇒ P(error∣wrong)=12\text{wrong basis: she resends } \ket{e}_{\bar\theta},\quad \abs{\braket{a_\theta|e_{\bar\theta}}}^2=\tfrac12\ \Rightarrow\ P(\text{error}\mid\text{wrong})=\tfrac12

    In a sifted round Bob measures in Alice's basis θ\theta, and the resent state is unbiased with respect to it.

  4. Q=12⋅0+12⋅12=14Q=\tfrac12\cdot0+\tfrac12\cdot\tfrac12=\tfrac14

    A 25% QBER in the sifted key, against roughly 0% on a clean link.

  5. Q=f4  if she attacks a fraction f,P(undetected on n test bits)=(1−Q)nQ=\tfrac f4\ \text{ if she attacks a fraction } f,\qquad P(\text{undetected on } n \text{ test bits})=(1-Q)^n

    Attacking everything, she survives nn test bits with probability (3/4)n(3/4)^n: about 3×10−133\times10^{-13} for n=100n=100.

Predict before you look

Eve runs a full intercept-resend attack. What is the smallest number nn of test bits that catches her with probability at least 99.9%, i.e. (3/4)n≤10−3(3/4)^n\le10^{-3}?

Show the answer

25 bits

n≥3/log⁡10(4/3)≈24.01n\ge3/\log_{10}(4/3)\approx24.01, so n=25n=25: (3/4)24≈1.003×10−3(3/4)^{24}\approx1.003\times10^{-3} just misses, (3/4)25≈7.5×10−4(3/4)^{25}\approx7.5\times10^{-4} succeeds. A cautious Eve attacks only a small fraction of the photons, which is why the threshold must be set by a security proof rather than by "any errors at all".

DerivationInformation gain implies disturbance
  1. U(∣ψ⟩∣e⟩)=∣ψ⟩∣eψ⟩,U(∣ϕ⟩∣e⟩)=∣ϕ⟩∣eϕ⟩U\big(\ket\psi\ket{e}\big)=\ket\psi\ket{e_\psi},\qquad U\big(\ket\phi\ket{e}\big)=\ket\phi\ket{e_\phi}

    Model any attack as a unitary coupling of the signal to Eve's probe ∣e⟩\ket e, and suppose it leaves two signal states undisturbed.

  2. ⟨ϕ∣ψ⟩ ⟨e∣e⟩=⟨ϕ∣ψ⟩ ⟨eϕ∣eψ⟩\braket{\phi|\psi}\,\braket{e|e}=\braket{\phi|\psi}\,\braket{e_\phi|e_\psi}

    Unitaries preserve inner products.

  3. ⟨ϕ∣ψ⟩≠0 ⟹ ⟨eϕ∣eψ⟩=1 ⟹ ∣eψ⟩=∣eϕ⟩\braket{\phi|\psi}\neq0\ \Longrightarrow\ \braket{e_\phi|e_\psi}=1\ \Longrightarrow\ \ket{e_\psi}=\ket{e_\phi}

    If the two states are non-orthogonal, Eve's probe ends in the same state for both: she has learned nothing that distinguishes them.

  4. In BB84 each ZZ state overlaps each XX state, so the chain e0=e+=e1=e−e_0=e_+=e_1=e_- follows. An attack that disturbs none of the four states teaches Eve nothing at all; any information she gains forces a nonzero error rate. ■\blacksquare

E91: keys from entanglement

Ekert (1991) proposed a different picture: a source, possibly controlled by Eve, distributes Bell pairs and both parties measure. With ∣Φ+⟩=12(∣00⟩+∣11⟩)\ket{\Phi^+}=\tfrac{1}{\sqrt2}(\ket{00}+\ket{11}) and a real basis {∣a⟩θ}\{\ket{a}_\theta\},

(⟨a∣θ⊗I)∣Φ+⟩=12 ∣a⟩θ.\big(\bra{a}_\theta\otimes\id\big)\ket{\Phi^+}=\tfrac{1}{\sqrt2}\,\ket{a}_\theta .

When Alice measures her half in basis θ\theta and gets aa, Bob's qubit is left in exactly the BB84 state ∣a⟩θ\ket{a}_\theta. Prepare-and-measure BB84 is therefore equivalent to an entanglement-based protocol, the observation at the heart of its security proofs.

Settings (Bloch angles in the XX–ZZ plane)Correlation E=cos⁡(θA−θB)E=\cos(\theta_A-\theta_B)Used for
Alice θA∈{0,π4,π2}\theta_A\in\{0,\tfrac\pi4,\tfrac\pi2\}, Bob θB∈{π4,π2,3π4}\theta_B\in\{\tfrac\pi4,\tfrac\pi2,\tfrac{3\pi}4\}depends on the pairrandom choice each round
(π4,π4)(\tfrac\pi4,\tfrac\pi4) and (π2,π2)(\tfrac\pi2,\tfrac\pi2)+1+1: identical bitsthe key (2 of 9 setting pairs)
(0,π4)(0,\tfrac\pi4), (0,3π4)(0,\tfrac{3\pi}4), (π2,π4)(\tfrac\pi2,\tfrac\pi4), (π2,3π4)(\tfrac\pi2,\tfrac{3\pi}4)12, −12, 12, 12\tfrac{1}{\sqrt2},\ -\tfrac{1}{\sqrt2},\ \tfrac{1}{\sqrt2},\ \tfrac{1}{\sqrt2}the CHSH test
E91 in the Φ+\Phi^+ convention of the widget below. Ekert's original used the singlet ∣Ψ−⟩\ket{\Psi^-}, whose equal settings give perfectly anti-correlated bits (Bob simply flips his), and his CHSH value came out as −22-2\sqrt2 in his sign convention.
S=E(0,π4)−E(0,3π4)+E(π2,π4)+E(π2,3π4)=4⋅12=22S=E\big(0,\tfrac\pi4\big)-E\big(0,\tfrac{3\pi}4\big)+E\big(\tfrac\pi2,\tfrac\pi4\big)+E\big(\tfrac\pi2,\tfrac{3\pi}4\big)=4\cdot\tfrac{1}{\sqrt2}=2\sqrt2
Any local-hidden-variable model, and any source whose pairs are merely classically correlated, obeys ∣S∣≤2\abs{S}\le2.

From raw key to secret key

Real links are noisy, so Alice and Bob must live with a nonzero QBER QQ and decide how much secret key it leaves. Error correction requires Bob to learn about h(Q)h(Q) bits of parity information per key bit (Shannon's limit), and since that information is public, it must be paid back. Privacy amplification then compresses the string by however much Eve might know, using a randomly chosen hash function.

How much can Eve know? The entanglement picture answers it. Bit errors in the ZZ key are XX-type errors on the shared pairs; Eve's knowledge of the ZZ key is controlled by phase (ZZ-type) errors, which would appear as bit errors had the same pairs been measured in XX. Because the basis is random and announced only afterwards, the phase-error rate of the key rounds is estimated by the error rate of the XX rounds.

DerivationThe asymptotic BB84 key rate
  1. r=1−h(QZ)⏟error correction−h(QX)⏟privacy amplificationr=1-\underbrace{h(Q_Z)}_{\text{error correction}}-\underbrace{h(Q_X)}_{\text{privacy amplification}}

    Secret bits per sifted bit for one-way post-processing, as n→∞n\to\infty (Shor & Preskill, 2000). QZQ_Z is the bit-error rate of the key, and QXQ_X bounds the phase-error rate.

  2. h(x)=−xlog⁡2x−(1−x)log⁡2(1−x)h(x)=-x\log_2x-(1-x)\log_2(1-x)

    The binary entropy: h(0)=0h(0)=0, h(12)=1h(\tfrac12)=1.

  3. QZ=QX=Q⟹r=1−2h(Q)Q_Z=Q_X=Q\quad\Longrightarrow\quad r=1-2h(Q)

    For a symmetric channel the two error rates coincide.

  4. r>0  ⟺  h(Q)<12  ⟺  Q<11.0%r>0\iff h(Q)<\tfrac12\iff Q<11.0\%

    h(0.110)≈0.500h(0.110)\approx0.500. This is the famous 11% threshold, and the reason the widget calls a run secure only when Q<11%Q<11\%.

Predict before you look

The measured QBER is Q=5%Q=5\%. What fraction of the sifted key survives error correction and privacy amplification, r=1−2h(0.05)r=1-2h(0.05)?

Show the answer

0.43

h(0.05)=0.05log⁡220+0.95log⁡210.95≈0.216+0.070=0.286h(0.05)=0.05\log_2 20+0.95\log_2\tfrac{1}{0.95}\approx0.216+0.070=0.286, so r≈1−0.573=0.43r\approx1-0.573=0.43. Even modest noise costs more than half the key, and the cost grows steeply: at Q=8%Q=8\% only about 0.200.20 survives.

Practical issueConsequenceCountermeasure
Fiber loss, about 0.20.2 dB/kmKey rate falls exponentially with distance; no repeaterless protocol beats −log⁡2(1−η)-\log_2(1-\eta) bits per mode for transmissivity η\etaTwin-field QKD (rate ∝η\propto\sqrt\eta), trusted relay nodes, satellites, eventually quantum repeaters
Weak laser pulses sometimes contain 2+ photonsPhoton-number-splitting attack: Eve keeps a copy without disturbanceDecoy states: randomly vary the intensity to monitor the single-photon yield
Imperfect detectorsBlinding and timing attacks have fully broken commercial systemsMeasurement-device-independent QKD; device-independent QKD
Finite number of roundsStatistical uncertainty in QQFinite-key analysis with composable security parameters

Key takeaways

  • BB84 encodes random bits in two mutually unbiased bases; sifting keeps the ~50% of rounds with matching bases, and test bits estimate the QBER.
  • For non-orthogonal states, information gain implies disturbance. Full intercept-resend causes Q=25%Q=25\%, and Eve survives nn test bits with probability (3/4)n(3/4)^n.
  • E91 distributes Bell pairs; matching settings give key, and a CHSH value near 222\sqrt2 certifies that Eve is decoupled (monogamy). BBM92 is its trusted-device version, equivalent to BB84.
  • With one-way post-processing the asymptotic key rate is 1−2h(Q)1-2h(Q) per sifted bit, positive for Q<11.0%Q<11.0\%.
  • QKD needs an authenticated classical channel (it grows a key, it does not create one), and real devices need protection against implementation attacks.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Eve performs intercept-resend on a random 20% of the photons and leaves the rest alone. What QBER do Alice and Bob observe in the sifted key?

  1. 20%
  2. 5%
  3. 25%
  4. 10%
Show the answer

B. 5%

Each attacked sifted bit is wrong with probability 14\tfrac14, so Q=0.2×14=5%Q=0.2\times\tfrac14=5\%. That is below the 11% threshold, which is fine: the security proof accounts for exactly this kind of partial information when it sets the privacy-amplification cost.

Question 2

Why do Alice and Bob discard the rounds in which their bases differ?

  1. Eve is guaranteed to have intercepted those photons
  2. Those photons are usually lost in the fiber
  3. Announcing the bases has revealed those bits to Eve
  4. Bob's outcome is a fair coin, independent of Alice's bit, so those rounds carry no shared key
Show the answer

D. Bob's outcome is a fair coin, independent of Alice's bit, so those rounds carry no shared key

The bases are mutually unbiased: a ZZ state measured in XX (or vice versa) gives a uniformly random result. These rounds would contribute 50% errors and no correlation.

Question 3

In E91, Alice and Bob's test rounds give S≈22S\approx2\sqrt2, the maximum quantum value. What does this let them conclude?

  1. Their pairs are (essentially) the maximally entangled state, so by monogamy Eve's system is uncorrelated with their outcomes
  2. An eavesdropper is present, because a classical channel would give S≤2S\le2
  3. Their key is correct, but Eve may still hold a copy of it
  4. The source must be a trusted device built by Alice
Show the answer

A. Their pairs are (essentially) the maximally entangled state, so by monogamy Eve's system is uncorrelated with their outcomes

A maximal CHSH violation can only come from a maximally entangled pure state (up to local changes of basis). A pure state of ABAB cannot be correlated with anything else, so Eve is decoupled. The source may even be built by Eve.

Question 4

The BB84 key rate is 1−2h(Q)1-2h(Q). Why is h(Q)h(Q) subtracted twice?

  1. Once for each of the two bases, ZZ and XX
  2. Because Alice and Bob each discard h(Q)h(Q) bits of their own strings
  3. Once to pay for the public error-correction information, and once for privacy amplification against Eve's information, which is bounded by the phase-error rate
  4. Because sifting removes half of the raw key
Show the answer

C. Once to pay for the public error-correction information, and once for privacy amplification against Eve's information, which is bounded by the phase-error rate

Error correction leaks about h(QZ)h(Q_Z) bits per key bit; Eve's knowledge is bounded by h(QX)h(Q_X), the entropy of the phase errors. For symmetric noise QZ=QX=QQ_Z=Q_X=Q.

Question 5

Why must the classical channel of QKD be authenticated?

  1. To keep the basis announcements secret from Eve
  2. Otherwise Eve can run separate QKD sessions with Alice and with Bob, impersonating each to the other
  3. To reduce the QBER below 11%
  4. So that Bob can correct errors without revealing parity bits
Show the answer

B. Otherwise Eve can run separate QKD sessions with Alice and with Bob, impersonating each to the other

Without authentication, a man in the middle establishes one key with Alice and another with Bob, and relays (and reads) all traffic. Eve may hear the classical messages; she must not be able to forge them.

Go deeper

Further reading

  • C. H. Bennett & G. Brassard, "Quantum cryptography: Public key distribution and coin tossing", Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing (1984).
  • A. K. Ekert, "Quantum cryptography based on Bell's theorem", Physical Review Letters 67, 661 (1991).
  • C. H. Bennett, G. Brassard & N. D. Mermin, "Quantum cryptography without Bell's theorem", Physical Review Letters 68, 557 (1992).
  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §12.6 (Cambridge, 10th anniv. ed., 2010).