Simple Algorithm
Quantum Computing · Rydberg State · 32 min

Security Proofs & Privacy Amplification

From error rates to secret key rates.

"Eve causes errors" is an intuition, not a proof. A real security proof must handle an adversary with unlimited quantum memory who attacks all signals jointly, and it must certify a key that stays secret however it is used later. This lesson builds that proof: composable ε\varepsilon-security, the Shor–Preskill reduction to quantum error-correcting codes, the entropic route via uncertainty relations, and the leftover hash lemma that turns min-entropy into key.

What you’ll learn

  • State the composable security criterion (correctness and secrecy in trace distance) and explain why accessible-information criteria are insufficient.
  • Reconstruct the Shor–Preskill argument: source replacement, CSS-code entanglement distillation, and its reduction to classical error correction plus privacy amplification.
  • Derive the rate 1−h(QX)−h(QZ)1-h(Q_X)-h(Q_Z) from the Devetak–Winter formula and the entropic uncertainty relation with quantum memory.
  • Prove the leftover hash lemma for classical side information and apply its quantum version to compute extractable key lengths.
  • Explain the structure of finite-key bounds and the known thresholds for BB84 with one-way and two-way post-processing.

What "secure" has to mean

Attacks are classified by Eve's power. In individual attacks she probes each signal separately and measures before post-processing. In collective attacks she attaches an independent probe to each signal but may store all probes in a quantum memory and measure them jointly at the end. In coherent (general) attacks her operation on all NN signals is arbitrary. A proof must cover coherent attacks, and it must survive composition: the key will be fed into a one-time pad, an authentication tag, or another QKD round.

The trace distance is the right measure because it is operational: no procedure whatsoever, including any later use of the key, can distinguish the real state from the ideal one τℓ⊗ρE\tau_\ell\otimes\rho_E with advantage greater than ε\varepsilon. Errors therefore add up linearly over many uses. Note what ε\varepsilon does not bound: the abort probability. Robustness (not aborting on an honest noisy channel) is a separate requirement.

Check your understanding

A QKD protocol is proven ε\varepsilon-secure with ε=10−10\varepsilon=10^{-10}. Which statement is guaranteed?

  1. Eve's accessible information about the key is at most 10−1010^{-10} bits, which is all that security requires
  2. In any later use of the key, the probability of any event (such as Eve guessing a message) exceeds its value for a perfect key by at most 10−1010^{-10}
  3. Alice's and Bob's keys may differ in up to a fraction 10−1010^{-10} of their positions
  4. The protocol aborts with probability at most 10−1010^{-10}
Show the answer

B. In any later use of the key, the probability of any event (such as Eve guessing a message) exceeds its value for a perfect key by at most 10−1010^{-10}

12∥ρreal−ρideal∥1≤ε\tfrac12\norm{\rho_{\rm real}-\rho_{\rm ideal}}_1\le\varepsilon means that every event has probability within ε\varepsilon of its ideal value. That is a statement about all future uses, which is what composability buys.

Shor–Preskill: BB84 as hidden entanglement distillation

Mayers (1996) gave the first proof of BB84 against coherent attacks, and Lo & Chau (1999) a conceptually cleaner one that, however, required Alice and Bob to own quantum computers. Shor & Preskill (2000) showed that Lo–Chau's entanglement-distillation protocol, built from CSS codes, can be reduced to plain BB84 with classical post-processing.

DerivationFrom CSS codes to the rate 1 − 2h(Q)
  1. Source replacement. Let Alice prepare ∣Φ+⟩⊗N\ket{\Phi^+}^{\otimes N} and measure her halves in random bases. Bob's halves are then exactly random BB84 states, so the two protocols are indistinguishable to Eve. Now let Eve hold the source: the shared state ρANBNE\rho_{A^NB^NE} is arbitrary, not i.i.d.

  2. X,Y errors flip Z-outcomes (bit errors),Z,Y errors flip X-outcomes (phase errors)X,Y\ \text{errors flip } Z\text{-outcomes (bit errors)},\qquad Z,Y\ \text{errors flip } X\text{-outcomes (phase errors)}

    Expand Eve's action on each pair in Pauli errors relative to ∣Φ+⟩\ket{\Phi^+}. Only the numbers of bit and phase errors matter for what follows.

  3. nph(key positions) ≲ n (QX+δ)except with probability e−Ω(nδ2)n_{\rm ph}(\text{key positions})\ \lesssim\ n\,(Q_X+\delta)\quad\text{except with probability } e^{-\Omega(n\delta^2)}

    Sampling. Basis choices and test positions are random and unknown to Eve when she acts, so the test positions are a random sample of the whole. The phase-error rate of the key pairs is estimated by the bit-error rate observed in XX-basis tests (a classical sampling bound of Hoeffding or Serfling type).

  4. C2⊂C1⊆F2n,k=dim⁡C1−dim⁡C2,kn→1−2h(t)C_2\subset C_1\subseteq\mathbb F_2^n,\qquad k=\dim C_1-\dim C_2,\qquad \frac kn\to1-2h(t)

    CSS codes. C1C_1 corrects tntn bit errors and C2⊥C_2^\perp corrects tntn phase errors. Random-coding arguments give such codes with rate approaching 1−2h(t)1-2h(t) (with high probability over the code).

  5. Distillation. Measuring the CSS stabilizers and correcting turns the nn noisy pairs into kk pairs of fidelity 1−ϵ1-\epsilon with ∣Φ+⟩⊗k\ket{\Phi^+}^{\otimes k}. A nearly pure state of ABAB is nearly decoupled from EE, so measuring these pairs in ZZ yields a key about which Eve knows essentially nothing.

  6. Reduction. Phase-error syndromes and corrections are ZZ-type and commute with the final ZZ measurement: they never change the key and can be skipped. Only their existence (guaranteed by the sampling step) is needed. The bit-error syndromes become classical error correction (Alice announces the C1C_1-syndrome of her string), and decoding becomes taking the coset of the corrected string in C1/C2C_1/C_2, a linear hash, which is privacy amplification.

  7. r=kn=1−h(QZ)−h(QX) → QZ=QX=Q  1−2h(Q),r>0  ⟺  Q<11.0%r=\frac kn=1-h(Q_Z)-h(Q_X)\ \xrightarrow{\ Q_Z=Q_X=Q\ }\ 1-2h(Q),\qquad r>0\iff Q<11.0\%

    Because the virtual distillation protocol works against an arbitrary state ρANBNE\rho_{A^NB^NE}, so does the classical protocol it reduces to. ■\blacksquare

Protocol and post-processingTolerable QBERSource
BB84, one-way11.0%11.0\%Shor–Preskill (2000)
BB84, one-way with noisy preprocessing≈12.4%\approx12.4\%Kraus, Gisin & Renner (2005)
Six-state, one-way≈12.6%\approx12.6\%hashing bound 1−H(1−3Q2,Q2,Q2,Q2)1-H\big(1-\tfrac{3Q}{2},\tfrac Q2,\tfrac Q2,\tfrac Q2\big)
BB84, any one-way scheme (upper bound)≈14.6%\approx14.6\%optimal cloning attack, sin⁡2π8\sin^2\tfrac\pi8
BB84, two-way (advantage distillation)≈18.9%\approx18.9\% to 20%20\%Gottesman & Lo (2003); Chau (2002)
BB84, any post-processing (upper bound)<25%<25\%intercept-resend makes the correlations separable
Known lower bounds (achievable) and upper bounds (impossible beyond) for symmetric noise. Advantage distillation helps because two-way communication lets Alice and Bob keep blocks that Eve's errors correlate badly with.

The entropic route: Devetak–Winter and uncertainty

DerivationThe BB84 rate in four lines
  1. H(ZA∣E) ≥ 1−H(XA∣B)H(Z_A|E)\ \ge\ 1-H(X_A|B)

    The uncertainty relation; XAX_A is the outcome Alice would have obtained in the XX basis.

  2. H(XA∣B) ≤ H(XA∣XB) ≤ h(QX)H(X_A|B)\ \le\ H(X_A|X_B)\ \le\ h(Q_X)

    Data processing (Bob measuring XX can only lose information), then Fano's inequality for a binary variable with error rate QXQ_X.

  3. H(ZA∣ZB) ≤ h(QZ)H(Z_A|Z_B)\ \le\ h(Q_Z)

    The error-correction cost, again by Fano.

  4. r ≥ H(ZA∣E)−H(ZA∣ZB) ≥ 1−h(QX)−h(QZ)r\ \ge\ H(Z_A|E)-H(Z_A|Z_B)\ \ge\ 1-h(Q_X)-h(Q_Z)

    Devetak–Winter with Bob's measured outcome. No codes and no symmetrization needed; the same structure handles any pair of bases.

Predict before you look

A misaligned link has QZ=2%Q_Z=2\% but QX=6%Q_X=6\%. What is the asymptotic key rate per sifted bit, 1−h(0.02)−h(0.06)1-h(0.02)-h(0.06)?

Show the answer

0.53

h(0.02)≈0.141h(0.02)\approx0.141 and h(0.06)≈0.327h(0.06)\approx0.327, so r≈0.53r\approx0.53. The phase errors, which control Eve's information, cost more here than the bit errors. In practice one also biases the basis choice toward ZZ so that almost all rounds are sifted (Lo, Chau & Ardehali), keeping the XX basis only for testing.

Collective-attack rates are not the end of the story, since Eve may attack coherently. Two tools close the gap for permutation-symmetric protocols. Renner's quantum de Finetti theorem (2007) and the post-selection technique of Christandl, König & Renner (2009) show that coherent attacks cost no more than collective ones asymptotically, at the price of finite-size corrections. Alternatively, the smooth-entropy uncertainty relation of Tomamichel & Renner (2011), Hmin⁡ε(Zn∣E)+Hmax⁡ε(Xn∣B)≥nlog⁡21cH_{\min}^\varepsilon(\mathbb Z^n|E)+H_{\max}^\varepsilon(\mathbb X^n|B)\ge n\log_2\frac1c, applies to arbitrary states directly and yields the tightest finite-key bounds.

Privacy amplification and finite keys

DerivationLeftover hash lemma (classical side information)
  1. Col(P)=∑zP(z)2=2−H2(P),H2 ≥ Hmin⁡\mathrm{Col}(P)=\sum_zP(z)^2=2^{-H_2(P)},\qquad H_2\ \ge\ H_{\min}

    The collision probability of two independent samples defines the collision entropy H2H_2.

  2. Col(F,F(X))=1∣F∣(Pr⁡[X=X′]+∑x≠x′P(x)P(x′)Pr⁡f[f(x)=f(x′)])≤2−H2(X)+2−ℓ∣F∣\mathrm{Col}\big(F,F(X)\big)=\frac{1}{\abs{\mathcal F}}\Big(\Pr[X=X']+\sum_{x\neq x'}P(x)P(x')\Pr_f\big[f(x)=f(x')\big]\Big)\le\frac{2^{-H_2(X)}+2^{-\ell}}{\abs{\mathcal F}}

    Two independent runs collide only if they drew the same function (probability 1/∣F∣1/\abs{\mathcal F}) and the outputs agree; then use two-universality.

  3. ∥P−UM∥1 ≤ M∑z(P(z)−1M)2=M Col(P)−1\norm{P-U_M}_1\ \le\ \sqrt{M\textstyle\sum_z\big(P(z)-\tfrac1M\big)^2}=\sqrt{M\,\mathrm{Col}(P)-1}

    Cauchy–Schwarz, for any distribution PP on MM points.

  4. 12∥PF,F(X)−UF×U2ℓ∥1 ≤ 122ℓ(2−H2(X)+2−ℓ)−1=12 2−12(H2(X)−ℓ)\tfrac12\norm{P_{F,F(X)}-U_{\mathcal F}\times U_{2^\ell}}_1\ \le\ \tfrac12\sqrt{2^\ell\big(2^{-H_2(X)}+2^{-\ell}\big)-1}=\tfrac12\,2^{-\frac12\left(H_2(X)-\ell\right)}

    Take M=∣F∣ 2ℓM=\abs{\mathcal F}\,2^\ell. The output is close to uniform even given the seed FF, so the seed can be chosen and announced publicly. ■\blacksquare

ℓ ≈ n[1−h(QX+μ)] − leakEC − O(log⁡1εsec+log⁡1εcor),μ∼ln⁡(1/εsec)k\ell\ \approx\ n\big[1-h(Q_X+\mu)\big]\ -\ \mathrm{leak}_{\rm EC}\ -\ \order{\log\tfrac1{\varepsilon_{\rm sec}}+\log\tfrac1{\varepsilon_{\rm cor}}},\qquad \mu\sim\sqrt{\frac{\ln(1/\varepsilon_{\rm sec})}{k}}
The structure of a finite-key bound for BB84 (Tomamichel, Lim, Gisin & Renner, 2012): nn key bits, kk test bits, μ\mu the statistical margin on the phase-error rate, and leakEC\mathrm{leak}_{\rm EC} slightly above n h(QZ)n\,h(Q_Z) for practical codes. Below roughly 10410^4 to 10510^5 signals the margins eat the entire key.

Key takeaways

  • Composable security: Pr⁡[KA≠KB]≤εcor\Pr[K_A\neq K_B]\le\varepsilon_{\rm cor} and ppass12∥ρKAE−τℓ⊗ρE∥1≤εsecp_{\rm pass}\tfrac12\norm{\rho_{K_AE}-\tau_\ell\otimes\rho_E}_1\le\varepsilon_{\rm sec}. Accessible-information criteria fail because of locking.
  • Shor–Preskill: BB84 is a disguised CSS entanglement-distillation protocol. Bit-error correction becomes classical error correction, phase-error correction becomes privacy amplification, and r=1−2h(Q)r=1-2h(Q) against coherent attacks.
  • Entropic proof: H(ZA∣E)≥1−H(XA∣B)H(Z_A|E)\ge1-H(X_A|B) plus Devetak–Winter gives r≥1−h(QX)−h(QZ)r\ge1-h(Q_X)-h(Q_Z).
  • Leftover hash lemma: two-universal hashing extracts ℓ≈Hmin⁡ε(X∣E)−2log⁡2(1/ε)\ell\approx H^\varepsilon_{\min}(X|E)-2\log_2(1/\varepsilon) uniform bits, even against quantum side information.
  • Thresholds for BB84: 11.0% (one-way), ≈12.4% (noisy preprocessing), ≈20% (two-way); nothing works at 25%.

Check yourself

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

Question 1

An honest but noisy BB84 link has symmetric Q=15%Q=15\%. Can Alice and Bob still extract a secret key?

  1. No: above 11% no secret key is possible
  2. Yes, with one-way post-processing, provided they first add noise to their raw key
  3. Only if they sacrifice more test bits to estimate QQ more precisely
  4. Yes, but only with two-way post-processing (advantage distillation); no one-way scheme works above about 14.6%
Show the answer

D. Yes, but only with two-way post-processing (advantage distillation); no one-way scheme works above about 14.6%

Two-way protocols are proven secure up to about 18.9% (Gottesman–Lo) and 20% (Chau). One-way schemes cannot exceed about 14.6%, where the optimal cloning attack gives Eve a copy as good as Bob's.

Question 2

In the Shor–Preskill reduction, why can Alice and Bob skip the phase-error correction entirely?

  1. Phase errors never occur in practice
  2. Phase corrections are ZZ-type and commute with the final ZZ-basis measurement, so they would not change the key; only their existence matters
  3. Eve cannot cause phase errors without also causing bit errors
  4. Privacy amplification removes bit errors, which makes phase correction redundant
Show the answer

B. Phase corrections are ZZ-type and commute with the final ZZ-basis measurement, so they would not change the key; only their existence matters

The virtual protocol would correct phase errors and output near-perfect ∣Φ+⟩\ket{\Phi^+} pairs; since those corrections commute with the ZZ measurement, the measured key is identical whether or not they are performed. Sampling guarantees the correction would succeed, which is what decouples Eve.

Question 3

After error correction Alice holds X∈{0,1}106X\in\{0,1\}^{10^6} with Hmin⁡(X∣E)≥4×105H_{\min}(X|E)\ge4\times10^5, accounting for everything Eve has learned. Roughly how long a key can two-universal hashing extract with secrecy parameter 2−502^{-50}?

  1. 2×1052\times10^5 bits
  2. 6×1056\times10^5 bits
  3. About 4×105−1004\times10^5-100 bits
  4. 106−10010^6-100 bits
Show the answer

C. About 4×105−1004\times10^5-100 bits

The leftover hash lemma needs 2−12(Hmin⁡−ℓ)≤2−502^{-\frac12(H_{\min}-\ell)}\le2^{-50}, i.e. ℓ≤Hmin⁡−100\ell\le H_{\min}-100. The security cost is additive and logarithmic in 1/ε1/\varepsilon, not a constant fraction of the key.

Question 4

What distinguishes a collective attack from a coherent attack?

  1. In a collective attack Eve probes each signal independently with the same interaction but may measure all her probes jointly at the end; a coherent attack allows an arbitrary joint operation on all signals
  2. In a collective attack Eve must measure each probe immediately
  3. Collective attacks act only on the classical channel
  4. Coherent attacks are restricted to intercept-resend
Show the answer

A. In a collective attack Eve probes each signal independently with the same interaction but may measure all her probes jointly at the end; a coherent attack allows an arbitrary joint operation on all signals

Collective attacks yield i.i.d. states ρABE⊗n\rho_{ABE}^{\otimes n}, where Devetak–Winter applies; de Finetti or post-selection arguments, or smooth-entropy uncertainty relations, extend security to arbitrary (coherent) attacks.

Further reading

  • P. W. Shor & J. Preskill, "Simple proof of security of the BB84 quantum key distribution protocol", Physical Review Letters 85, 441 (2000).
  • R. Renner, Security of Quantum Key Distribution, PhD thesis, ETH Zurich (2005); arXiv:quant-ph/0512258.
  • I. Devetak & A. Winter, "Distillation of secret key and entanglement from quantum states", Proceedings of the Royal Society A 461, 207 (2005).
  • M. Tomamichel, C. C. W. Lim, N. Gisin & R. Renner, "Tight finite-key analysis for quantum cryptography", Nature Communications 3, 634 (2012).
  • V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus & M. Peev, "The security of practical quantum key distribution", Reviews of Modern Physics 81, 1301 (2009).