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 -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 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 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 with advantage greater than . Errors therefore add up linearly over many uses. Note what does not bound: the abort probability. Robustness (not aborting on an honest noisy channel) is a separate requirement.
A QKD protocol is proven -secure with . Which statement is guaranteed?
- Eve's accessible information about the key is at most bits, which is all that security requires
- 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
- Alice's and Bob's keys may differ in up to a fraction of their positions
- The protocol aborts with probability at most
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
means that every event has probability within 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.
Source replacement. Let Alice prepare 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 is arbitrary, not i.i.d.
Expand Eve's action on each pair in Pauli errors relative to . Only the numbers of bit and phase errors matter for what follows.
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 -basis tests (a classical sampling bound of Hoeffding or Serfling type).
CSS codes. corrects bit errors and corrects phase errors. Random-coding arguments give such codes with rate approaching (with high probability over the code).
Distillation. Measuring the CSS stabilizers and correcting turns the noisy pairs into pairs of fidelity with . A nearly pure state of is nearly decoupled from , so measuring these pairs in yields a key about which Eve knows essentially nothing.
Reduction. Phase-error syndromes and corrections are -type and commute with the final 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 -syndrome of her string), and decoding becomes taking the coset of the corrected string in , a linear hash, which is privacy amplification.
Because the virtual distillation protocol works against an arbitrary state , so does the classical protocol it reduces to.
| Protocol and post-processing | Tolerable QBER | Source |
|---|---|---|
| BB84, one-way | Shor–Preskill (2000) | |
| BB84, one-way with noisy preprocessing | Kraus, Gisin & Renner (2005) | |
| Six-state, one-way | hashing bound | |
| BB84, any one-way scheme (upper bound) | optimal cloning attack, | |
| BB84, two-way (advantage distillation) | to | Gottesman & Lo (2003); Chau (2002) |
| BB84, any post-processing (upper bound) | intercept-resend makes the correlations separable |
The entropic route: Devetak–Winter and uncertainty
The uncertainty relation; is the outcome Alice would have obtained in the basis.
Data processing (Bob measuring can only lose information), then Fano's inequality for a binary variable with error rate .
The error-correction cost, again by Fano.
Devetak–Winter with Bob's measured outcome. No codes and no symmetrization needed; the same structure handles any pair of bases.
A misaligned link has but . What is the asymptotic key rate per sifted bit, ?
Show the answer
0.53
and , so . The phase errors, which control Eve's information, cost more here than the bit errors. In practice one also biases the basis choice toward so that almost all rounds are sifted (Lo, Chau & Ardehali), keeping the 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), , applies to arbitrary states directly and yields the tightest finite-key bounds.
Privacy amplification and finite keys
The collision probability of two independent samples defines the collision entropy .
Two independent runs collide only if they drew the same function (probability ) and the outputs agree; then use two-universality.
Cauchy–Schwarz, for any distribution on points.
Take . The output is close to uniform even given the seed , so the seed can be chosen and announced publicly.
Key takeaways
- Composable security: and . 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 against coherent attacks.
- Entropic proof: plus Devetak–Winter gives .
- Leftover hash lemma: two-universal hashing extracts 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.
An honest but noisy BB84 link has symmetric . Can Alice and Bob still extract a secret key?
- No: above 11% no secret key is possible
- Yes, with one-way post-processing, provided they first add noise to their raw key
- Only if they sacrifice more test bits to estimate more precisely
- 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.
In the Shor–Preskill reduction, why can Alice and Bob skip the phase-error correction entirely?
- Phase errors never occur in practice
- Phase corrections are -type and commute with the final -basis measurement, so they would not change the key; only their existence matters
- Eve cannot cause phase errors without also causing bit errors
- Privacy amplification removes bit errors, which makes phase correction redundant
Show the answer
B. Phase corrections are -type and commute with the final -basis measurement, so they would not change the key; only their existence matters
The virtual protocol would correct phase errors and output near-perfect pairs; since those corrections commute with the measurement, the measured key is identical whether or not they are performed. Sampling guarantees the correction would succeed, which is what decouples Eve.
After error correction Alice holds with , accounting for everything Eve has learned. Roughly how long a key can two-universal hashing extract with secrecy parameter ?
- bits
- bits
- About bits
- bits
Show the answer
C. About bits
The leftover hash lemma needs , i.e. . The security cost is additive and logarithmic in , not a constant fraction of the key.
What distinguishes a collective attack from a coherent attack?
- 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
- In a collective attack Eve must measure each probe immediately
- Collective attacks act only on the classical channel
- 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 , 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).