Information Reconciliation and Privacy Amplification

Every quantum key distribution run ends not with a key but with a disappointment: two strings that are almost, but not quite, the same, and not quite secret. After BB84 or E91 sifting, Alice holds a random string $X$ and Bob holds a correlated string $Y$ that disagrees with it wherever channel noise, detector dark counts, or an eavesdropper flipped a bit — a fraction summarized by the quantum bit error rate $Q$ . Worse, an adversary Eve may hold side information $E$ correlated with $X$ . The raw key is therefore neither correct (Alice $\ne$ Bob) nor secret (Eve knows something). This article is the classical back end that repairs both defects — the last block of every QKD security proof, identical no matter which quantum protocol produced the raw bits. The repair happens in two sharply distinct stages, both over a public but authenticated channel. Information reconciliation is error correction: Alice and Bob trade parity information until Bob's string equals Alice's, at the unavoidable cost — set by Slepian–Wolf — of revealing about $H(X|Y)$ bits to everyone, Eve included. Privacy amplification is secrecy distillation: they publicly pick a hash $g$ from a two-universal family and keep only $K=g(X)$ , a shorter string across which every scrap of Eve's residual knowledge is smeared to uselessness. The Leftover Hash Lemma, in its smooth-min-entropy form, quantifies how short the output must be to be secure, and the Devetak–Winter rate $r=H(X|E)-H(X|Y)$ gives the net yield: Eve's uncertainty minus the public leakage.

Key takeaways

After sifting, Alice and Bob share strings that disagree at rate $Q$ and that Eve partly knows; two purely classical steps fix correctness and secrecy over a public authenticated channel.
Information reconciliation costs at least $H(X|Y)$ public bits (Slepian–Wolf); real codes — Cascade, LDPC, polar — leak $f\,n\,h(Q)$ with efficiency $f\gtrsim1$ , and every leaked bit is also handed to Eve.
Privacy amplification hashes the $n$ reconciled bits down to $\ell<n$ with a random two-universal function, leaving a key $\varepsilon$ -close to uniform and independent of Eve.
The Leftover Hash Lemma sets the safe output length: distance from ideal is $\tfrac12\,2^{-(H_\infty-\ell)/2}$ , controlled by the smooth conditional min-entropy $H_\infty^\varepsilon(X|E)$ — not the Shannon entropy.
For symmetric one-way BB84 the Devetak–Winter rate is the Shor–Preskill line $r=1-2h(Q)$ , which vanishes at the famous tolerable error rate $Q\approx11.0\%$ .
Key idea: reconciliation pays $\approx H(X|Y)$ public bits to make Alice and Bob identical; privacy amplification then hashes away all of Eve's residual knowledge, and the net secret-key length is governed by the Leftover Hash Lemma applied to the smooth conditional min-entropy of Alice's string given Eve's side information.

Where this lives today

The two stages are the working back end of every deployed and experimental QKD system, and the place where most of a link's engineering effort actually goes. Commercial stacks (ID Quantique, Toshiba) treat post-processing as a protocol-independent library: a high-throughput LDPC or polar reconciliation core with efficiency $f\lesssim1.1$ , followed by Toeplitz-matrix privacy amplification that hashes megabit blocks in real time on an FPGA. The 2017 Micius satellite experiments and the Jinan–Beijing fibre backbone both certify their final keys through exactly this smooth-min-entropy, finite-key composable analysis — quoting an explicit $\varepsilon_{\text{tot}}$ rather than an asymptotic rate. The same two-universal hashing reappears outside QKD as the strong seeded extractor in quantum random number generators and device-independent randomness expansion, where the input min-entropy is certified by a Bell-inequality violation instead of a QBER. Open problems stay sharply practical: tightening finite-key bounds so short blocks ( $10^4$ – $10^5$ bits) yield usable keys, and reconciling at high $Q$ for long-distance and free-space links.

The physical picture

Picture two friends who each copied a long random number off a noisy phone line. First they must agree on the number despite a few wrong digits — that is reconciliation, done by comparing checksums until every disagreement is hunted down. But anyone tapping the line heard those checksums and may already have half-overheard the original. So next they both apply the same publicly agreed scrambling rule — a random hash — and keep only a short digest. Whatever partial knowledge the eavesdropper had about the long number is now spread thinly across the short digest, until it tells her nothing. Two stages, two jobs: make the strings equal, then make them secret.

Figure

The two classical post-processing stages: reconciliation trades f·n·h(Q) public parity bits to turn Bob's noisy Y into Alice's X, then privacy amplification hashes the n reconciled bits down to ℓ = H∞ − leak − 2log₂(1/2ε) secret bits Eve cannot predict

The decisive quantity is not how uncertain Eve is on average, but how well she can guess in the best case — the min-entropy $H_\infty=-\log_2 p_{\text{guess}}$ . Two-universal hashing converts guessing-probability into near-uniformity: if Eve could guess the input with probability $2^{-H_\infty}$ , an $\ell$ -bit hash lands within $\tfrac12\,2^{-(H_\infty-\ell)/2}$ of perfect secrecy. A security gap $H_\infty-\ell$ of only about sixty-four bits already buys $\varepsilon\approx10^{-10}$ — cryptographically indistinguishable from random. The randomness that becomes the key comes from the public choice of hash, not from the input, which is why the scheme works even against an input distribution shaped by the adversary. That leaves one number that decides whether any secret key exists at all: the balance between how much Alice and Bob agree and how much Eve knows. The second figure plots it for the canonical case — symmetric one-way BB84 against collective attacks — where the whole story collapses to the line $r=1-2h(Q)$ , positive up to the tolerable error rate and zero beyond it.

Figure

The Shor–Preskill secret-key rate r = 1 − 2h(Q) for one-way BB84 against collective attacks: the yield falls from 1 secret bit per sifted bit at Q = 0 and vanishes at the tolerable-error threshold Q ≈ 11.0% where h(Q) = 1/2

The core equations

Reconciliation is bounded below by a classical coding theorem. To let a receiver already holding a correlated string $Y$ reconstruct $X$ , the minimum public communication is the conditional entropy $H(X|Y)$ — no code, however clever, can leak less and still succeed. This is the Slepian–Wolf bound, and it is the floor every practical reconciliation code is measured against.

H(X|Y) = H(X,Y) - H(Y) \qquad (1)

where: $X$ — Alice's sifted string; $Y$ — Bob's correlated sifted string; $H(\cdot)$ — Shannon entropy in bits. Reading: $H(X|Y)$ is Alice's residual randomness once Bob's string is known; it is the least Bob must be told to catch up, and every told bit is public. For the symmetric binary channel that models a depolarized QKD link, the per-symbol conditional entropy is just the binary entropy of the error rate. This one function controls both the reconciliation cost and, as it turns out, Eve's information in the symmetric case.

h(Q) = -Q\log_2 Q - (1-Q)\log_2(1-Q) \qquad (2)

where: $Q$ — quantum bit error rate (fraction of disagreeing sifted bits); $h$ — binary Shannon entropy function, rising from $0$ at $Q=0$ to $1$ at $Q=\tfrac12$ . Reading: $h(Q)$ is the reconciliation cost per bit; $h(0.05)\approx0.286$ , $h(0.11)\approx0.500$ . Security, unlike reconciliation, is not governed by Shannon entropy but by the adversary's best-case guessing power. The conditional min-entropy is exactly minus the log of Eve's optimal probability of guessing $X$ from her quantum system $E$ .

H_\infty(X|E) = -\log_2 p_{\text{guess}}(X|E),\qquad p_{\text{guess}}(X|E)=\max_{\{M_x\}}\sum_x p(x)\,\mathrm{Tr}(M_x\rho_E^x) \qquad (3)

where: $p_{\text{guess}}$ — optimal probability Eve guesses $X$ ; the maximum is over all POVMs $\{M_x\}$ she can measure on her conditional states $\rho_E^x$ . Reading: a source with high Shannon but low min-entropy has one likely value and is unsafe to hash — only $H_\infty$ certifies worst-case unpredictability. The engine of privacy amplification is the Leftover Hash Lemma. Hashing a source of min-entropy $H_\infty(X|E')$ with a random two-universal function to $\ell$ bits produces a key whose trace distance from an ideal key — uniform and product with Eve — is exponentially small in the security gap $H_\infty-\ell$ .

\Delta\!\left(\rho_{KE'},\, \tfrac{\mathbb{1}}{2^\ell}\otimes\rho_{E'}\right) \le \tfrac12\sqrt{2^{\,\ell - H_\infty(X|E')}} \qquad (4)

where: $K=g(X)$ — final key, $g$ from a two-universal family; $E'$ — Eve's total information, including the reconciliation transcript and the public choice of $g$ ; $\ell$ — output length; $\Delta$ — trace distance (the composable security parameter). Reading: each extra bit of gap $H_\infty-\ell$ halves the square-root's exponent — sixty-four bits of gap buys $\varepsilon\approx10^{-10}$ . Combining the two stages with an explicit failure budget gives the extractable length in the realistic finite-key regime, where i.i.d. entropies are replaced by the smooth conditional min-entropy $H_\infty^\varepsilon$ .

\ell \;\le\; H_\infty^{\varepsilon}(X|E) - \text{leak}_{\text{EC}} - 2\log_2\!\frac{1}{2\varepsilon_{\text{PA}}} \qquad (5)

where: $H_\infty^{\varepsilon}(X|E)$ — smooth conditional min-entropy of Alice given Eve before reconciliation; $\text{leak}_{\text{EC}}$ — bits revealed during reconciliation; $\varepsilon_{\text{PA}}$ — privacy-amplification failure probability. Reading: start from Eve's uncertainty, subtract what reconciliation leaked, then pay a fixed $2\log_2(1/2\varepsilon_{\text{PA}})$ security toll. In the asymptotic i.i.d. limit equation (5) becomes a difference of conditional entropies — the Devetak–Winter rate — the achievable secret bits per sifted bit under collective attacks.

r = H(X|E) - H(X|Y) = I(X{:}Y) - I(X{:}E) \qquad (6)

where: $H(X|E)$ — Eve's uncertainty about Alice's bit; $H(X|Y)$ — the reconciliation cost; equivalently the Alice–Bob mutual information minus the Alice–Eve mutual information. Reading: only the surplus of Bob's correlation over Eve's correlation becomes key; when the two match, $r=0$ .

Derivation AThe secret-key rate as a difference of conditional entropies

The goal is to show why the achievable secret-key rate is the difference $r=H(X|E)-H(X|Y)$ rather than simply Eve's uncertainty $H(X|E)$ , to recast it in the mutual-information form $I(X{:}Y)-I(X{:}E)$ , and then to specialize to symmetric BB84 to recover the Shor–Preskill line $r=1-2h(Q)$ and its $\approx11\%$ threshold. We work per sifted bit on a depolarizing channel that produces error rate $Q$ symmetrically in both bases, so Alice's raw bit is uniform, $H(X)=1$ .

Step 1. Reconciliation must make Bob's bit equal Alice's, and by Slepian–Wolf this costs $H(X|Y)$ public bits per symbol; for the symmetric channel $H(X|Y)=h(Q)$ . Why: Alice and Bob disagree with probability $Q$ , so Bob's residual uncertainty about Alice's bit is exactly the binary entropy of the flip probability.

Step 2. Every one of those reconciliation bits is broadcast on the public channel, so it also lands in Eve's hands; the secret material left over is Eve's uncertainty minus this public leakage, $r=H(X|E)-H(X|Y)$ . Why: subtracting the leak is the whole reason the rate is a difference — forgetting the transcript would double-count the leaked bits as secret.

Step 3. Rewrite using $I(X{:}Y)=H(X)-H(X|Y)$ and $I(X{:}E)=H(X)-H(X|E)$ ; the common $H(X)$ cancels, giving $r=I(X{:}Y)-I(X{:}E)$ — Alice–Bob correlation minus Alice–Eve correlation. Why: the mutual-information form makes the security condition intuitive — a key exists precisely when Bob is more correlated with Alice than Eve is.

Step 4. For symmetric BB84 the optimal collective attack ties Eve's information to the same binary entropy, $I(X{:}E)\le h(Q)$ , by the symmetry between bit and phase errors and the entropic uncertainty relation, while $I(X{:}Y)=1-h(Q)$ ; substituting gives $r=[1-h(Q)]-h(Q)=1-2h(Q)$ . Why: this is the Shor–Preskill rate, and it says one reconciliation cost plus one equal cost to Eve are both charged against the unit correlation.

Step 5. Set $r=0$ : $1-2h(Q)=0\Rightarrow h(Q)=\tfrac12$ , whose numerical root is $Q\approx0.1100$ . Why: at this error rate the public leakage plus Eve's information exhausts the Alice–Bob correlation, so no secret key survives one-way processing — the famous $\approx11\%$ tolerable QBER. *Verified: $h(0.11002)=0.5000$ and $1-2h(0.11)=0.00017\approx0$ ; standard Shor–Preskill result (Preskill Ch. 4).*

Go deeper · Derivation B · 1 minThe Leftover Hash Lemma from the collision probability

Derivation BThe Leftover Hash Lemma from the collision probability

The goal is to prove the classical Leftover Hash Lemma — that a two-universal hash of a source with min-entropy $H_\infty$ down to $\ell$ bits lands within $\tfrac12\,2^{-(H_\infty-\ell)/2}$ of uniform — because this bound is the exact promise privacy amplification cashes in, and its smooth-min-entropy generalization is equation (4). Take a source $X$ on $\{0,1\}^n$ with every probability bounded by $p_x\le2^{-H_\infty}$ , and a hash $g$ drawn uniformly from a two-universal family $\mathcal{G}$ into $\ell$ bits, so that $\Pr_g[g(x)=g(x')]\le2^{-\ell}$ for all $x\ne x'$ .

Step 1. Write the statistical distance to uniform as $\Delta=\tfrac12\sum_k|q_k-2^{-\ell}|$ with $q_k=\Pr[g(X)=k]$ , then apply Cauchy–Schwarz over the $2^\ell$ outcomes to get $\Delta\le\tfrac12\sqrt{2^\ell\sum_k(q_k-2^{-\ell})^2}$ . Why: the $L^2$ (collision) norm is what two-universality controls, so trading the $L^1$ distance for it is the move that makes the family's defining property usable.

Step 2. Average the collision term over the hash choice: $\mathbb{E}_g\sum_k q_k^2=\sum_{x,x'}p_x p_{x'}\Pr_g[g(x)=g(x')]$ , splitting into the diagonal $x=x'$ and off-diagonal $x\ne x'$ pieces. Why: expanding $q_k^2$ as a double sum over pre-images is what lets the collision bound act term by term.

Step 3. Bound each piece: the diagonal gives $\sum_x p_x^2\le\max_x p_x\le2^{-H_\infty}$ , and the off-diagonal uses two-universality to give at most $2^{-\ell}\sum_{x\ne x'}p_x p_{x'}\le2^{-\ell}$ , so $\mathbb{E}_g\sum_k q_k^2\le2^{-H_\infty}+2^{-\ell}$ . Why: this is the only place the two properties enter — min-entropy caps the self-collisions, two-universality caps the cross-collisions.

Step 4. Subtract the uniform baseline: $\mathbb{E}_g\sum_k(q_k-2^{-\ell})^2=\mathbb{E}_g\sum_k q_k^2-2^{-\ell}\le2^{-H_\infty}$ , and insert into Step 1 to obtain $\Delta\le\tfrac12\sqrt{2^\ell\,2^{-H_\infty}}=\tfrac12\,2^{-(H_\infty-\ell)/2}$ . Why: the $-2^{-\ell}$ shift exactly cancels the cross-collision term, leaving the clean gap $H_\infty-\ell$ in the exponent — the security margin the designer tunes. *Verified: algebra reproduces Bennett–Brassard–Crépeau–Maurer (1995) and reduces to the standard form $\tfrac12\,2^{-(H_\infty-\ell)/2}$ ; the quantum version replaces $H_\infty$ by $H_\infty^\varepsilon(X|E)$ and adds $2\bar\varepsilon$ (Renner 2005).*

Go deeper · Derivation C · 1 minReconciliation leakage and the efficiency factor

Derivation CReconciliation leakage and the efficiency factor

The goal is to track how much information a real interactive reconciliation actually spills relative to the Slepian–Wolf floor, to define the efficiency factor $f$ that catalogues report, and to show how the excess $n(f-1)h(Q)$ is subtracted straight out of the final key length. Cascade, the canonical example, reveals one block parity per binary-search step for each detected error, so the leaked count exceeds the theoretical minimum by a protocol-dependent overhead.

Step 1. The information-theoretic floor is fixed by the converse of Slepian–Wolf: no protocol correcting all errors can leak fewer than $\text{leak}_{\min}=n\,H(X|Y)=n\,h(Q)$ bits. Why: this floor is a hard converse, not an engineering target — it is what makes reconciliation a fundamental cost rather than an implementation detail.

Step 2. Define the efficiency factor as the ratio of actual to minimal leakage, $f(Q)=\text{leak}_{\text{EC}}/[n\,h(Q)]\ge1$ , so that $\text{leak}_{\text{EC}}=f(Q)\,n\,h(Q)$ ; empirically Cascade gives $f\approx1.05$ at low $Q$ , drifting toward $1.2$ as $Q$ grows, while well-designed LDPC and polar codes push $f$ toward $1$ . Why: $f$ is the single knob that converts an abstract bound into a real code's performance, and it is exactly what a QKD data sheet quotes.

Step 3. Fold the realistic leak into the asymptotic key length: $\ell=n[1-2h(Q)]-n(f-1)h(Q)-O(\sqrt{n})$ , so the inefficiency $n(f-1)h(Q)$ comes straight off the top, lowering both the rate and the tolerable error rate. Why: this line shows the practical cost of an imperfect code is not hidden anywhere — it is a direct, bit-for-bit subtraction from the secret key, which is why closing the gap to $f=1$ is worth real engineering effort. *Verified: consistent with Brassard–Salvail (1993) and reported QKD implementations with $f\in[1.05,1.2]$ ; at $Q=0.05,\ f=1.1$ the ideal rate $0.427$ drops to $0.399$ secret bits per sifted bit.*

Limiting cases

Behaviour of the secret-key fraction $r$ for symmetric BB84 against collective attacks as the QBER $Q$ varies:

Case	Result	Meaning
Noiseless channel	$Q\to0,\ r\to1$	No reconciliation cost and nothing leaked to Eve; the whole sifted key survives, one secret bit per sifted bit.
Symmetric one-way threshold	$r=1-2h(Q)=0\Rightarrow Q\approx11.0\%$	The Shor–Preskill rate vanishes where $h(Q)=\tfrac12$ ; above this QBER, one-way post-processing yields no key.
Six-state / two-way	$Q_{\text{tol}}\approx12.6\%$ (six-state), $\approx12.4\%$ (BB84 two-way)	Extra basis information or two-way advantage distillation raises the tolerable error rate above the one-way BB84 value.
Finite block length	$\ell\approx n[1-2h(Q)]-\Delta(n,\varepsilon),\ \Delta\sim\sqrt{n}$	Statistical penalties scale as $\sqrt{n}$ ; for small blocks the asymptotic rate is unreachable and $\ell$ can be zero even below threshold.

Common trapConfusing Shannon entropy with min-entropy — and forgetting the transcript leak

Two errors sink more QKD rate estimates than any physics mistake. First, security in privacy amplification is set by the smooth conditional min-entropy $H_\infty^\varepsilon(X|E)$ , never by the Shannon entropy $H(X|E)$ . A distribution can carry large Shannon entropy while hiding one dangerously probable value — low min-entropy — and hashing it leaves a guessable key; only $H_\infty$ measures worst-case unpredictability, so only $H_\infty$ belongs in the Leftover Hash Lemma. Second, every bit revealed during reconciliation is public and therefore Eve's; it must be subtracted from the extractable length as $\text{leak}_{\text{EC}}$ . Quoting Eve's uncertainty without deducting the transcript leak, or plugging Shannon entropy into the hash bound, both overstate the secret-key rate — sometimes enough to certify a key that is not actually secret.

Worked examples

1 · Secret-key rate of BB84 at 5% QBER, ideal and realistic (fully worked)

A BB84 link runs with symmetric QBER $Q=0.05$ and reconciles with a Cascade code of efficiency $f=1.10$ . From $n=10^6$ sifted bits, find the asymptotic secret-key length against collective attacks, first in the ideal-reconciliation limit and then with the real code.

Step 1. Compute the binary entropy of the error rate: $h(0.05)=-0.05\log_2 0.05-0.95\log_2 0.95=0.216+0.070=\mathbf{0.2864}$ bits per symbol. This is both the reconciliation cost $H(X|Y)$ and Eve's information $I(X{:}E)$ in the symmetric case.

Step 2. Ideal reconciliation ( $f=1$ ): the Shor–Preskill rate is $r=1-2h(Q)=1-2(0.2864)=\mathbf{0.4272}$ secret bits per sifted bit, so $\ell_{\text{ideal}}=0.4272\times10^6\approx\mathbf{4.27\times10^5}$ bits.

Step 3. Realistic reconciliation: the leak grows to $\text{leak}_{\text{EC}}/n=f\,h(Q)=1.10\times0.2864=0.3150$ per bit, while Eve's information stays $h(Q)=0.2864$ , so $\ell/n=1-0.3150-0.2864=\mathbf{0.3986}$ and $\ell_{\text{real}}\approx\mathbf{3.99\times10^5}$ bits.

Step 4. Interpret the gap: the imperfect code's overhead $n(f-1)h(Q)=10^6\times0.10\times0.2864\approx2.86\times10^4$ bits is exactly the difference $4.27\times10^5-3.99\times10^5$ . Ideal $\ell\approx4.27\times10^5$ ; realistic $\ell\approx3.99\times10^5$ ; the $2.9\times10^4$ -bit loss is the reconciliation inefficiency, recoverable with a better code.

2 · Extractable length from the Leftover Hash Lemma (fully worked)

After sifting, an $n=10^4$ -bit block is estimated to have smooth conditional min-entropy $H_\infty^\varepsilon(X|E)=0.80\,n=8000$ bits against Eve. Reconciliation then leaks $\text{leak}_{\text{EC}}=1500$ bits. For a privacy-amplification failure probability $\varepsilon_{\text{PA}}=10^{-10}$ , how long a secret key can be extracted, and what security gap does it leave?

Step 1. Evaluate the security toll in equation (5): $2\log_2\!\big(1/2\varepsilon_{\text{PA}}\big)=2\log_2\!\big(1/(2\times10^{-10})\big)=2\log_2(5\times10^{9})=2\times32.22=\mathbf{64.4}$ bits.

Step 2. Assemble the extractable length: $\ell\le H_\infty^\varepsilon(X|E)-\text{leak}_{\text{EC}}-64.4=8000-1500-64.4=\mathbf{6435}$ bits (rounding down). So the $10^4$ raw bits distil to about $6435$ certified-secret bits.

Step 3. Check the gap self-consistently against the Leftover Hash Lemma. After subtracting the leak, Eve's effective min-entropy about the reconciled string is $8000-1500=6500$ bits; the output is $\ell=6435$ , leaving a gap of $6500-6435=65\approx64.4$ bits. Plugging into equation (4), $\Delta\le\tfrac12\,2^{-64.4/2}=\tfrac12\,2^{-32.2}\approx10^{-10}$ , matching the requested $\varepsilon_{\text{PA}}$ . The block yields $\ell\approx6435$ secret bits; the $\approx64$ -bit gap is precisely what enforces $\varepsilon_{\text{PA}}=10^{-10}$ .

Physics of the portrait

Reconciliation and privacy amplification are not the work of one person but of a two-decade collaboration that turned a cryptographic hope — that a partly-leaked key can be made perfectly secret — into a theorem with an explicit $\varepsilon$ .

Origins · 1 minprivacy amplification and how this was discovered

privacy amplification

the distillation of near-perfect secrecy from a partly-known key by public two-universal hashing · classical post-processing for quantum key distribution

Privacy amplification began as a fix for a leak. When Charles Bennett and Gilles Brassard designed BB84 in 1984 they could sift and estimate errors, but a partly-compromised key was still partly compromised. In 1988 Bennett, Brassard, and Jean-Marc Robert showed the leak could be distilled away: hash the key with a random function and the eavesdropper's partial knowledge collapses, a result they christened privacy amplification. Reconciliation matured alongside it — Brassard and Salvail's 1993 Cascade protocol made the error-correction stage interactive and near-optimal, approaching the Slepian–Wolf floor. The 1995 synthesis by Bennett, Brassard, Crépeau, and Ueli Maurer put both on the firm footing of two-universal hashing and the Leftover Hash Lemma. The security picture snapped into focus around 2000–2005: Peter Shor and John Preskill gave a transparent proof of BB84 with the rate $1-2h(Q)$ and its $11\%$ threshold, while Renato Renner's thesis and the Devetak–Winter theorem recast everything in the language of smooth min-entropy, making the analysis composable and finite-size-exact. What had been a clever trick became the universal, protocol-independent back end that every modern QKD system runs — the mathematics that converts a noisy, half-overheard string into a key you can bet a message on.

History

1988

— Bennett, Brassard, Robert introduce privacy amplification by public discussion

1993

— Brassard and Salvail publish the Cascade reconciliation protocol

1995

— Bennett, Brassard, Crépeau, Maurer generalize it with two-universal hashing

2000

— Shor and Preskill prove BB84 security with rate 1 − 2h(Q)

2005

— Renner and Devetak–Winter recast security via smooth min-entropy

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §12.6 · Preskill, Lecture Notes on Quantum Information, Ch. 4 (cryptography) · Wilde, Quantum Information Theory, Ch. 21–23 (private capacity, randomness extraction) · Watrous, The Theory of Quantum Information (min-entropy and the operational chapter) · Renner, Security of Quantum Key Distribution (PhD thesis, ETH 2005) · Bennett, Brassard, Crépeau, Maurer, Generalized Privacy Amplification, IEEE Trans. IT 41 (1995) · Brassard & Salvail, Secret-Key Reconciliation by Public Discussion (Cascade), EUROCRYPT 1993 · Tomamichel, Lim, Gisin, Renner, Tight finite-key analysis for QKD, Nat. Commun. 3, 634 (2012).

Provenance. All equations and numbers are standard and re-verified here: the binary-entropy threshold $h(Q)=\tfrac12\Rightarrow Q\approx11.0\%$ (Shor–Preskill); the Devetak–Winter rate $r=I(X{:}Y)-I(X{:}E)=H(X|E)-H(X|Y)$ ; the Leftover Hash Lemma distance $\tfrac12\,2^{-(H_\infty-\ell)/2}$ (Bennett–Brassard–Crépeau–Maurer 1995, Renner 2005); the Slepian–Wolf reconciliation floor $H(X|Y)$ ; the two-universality collision bound $2^{-\ell}$ . A verifier should recompute $h(0.05)=0.2864$ and $h(0.11002)=0.5000$ , confirm the LHL Cauchy–Schwarz/collision derivation, check the finite-key toll $2\log_2(1/2\varepsilon_{\text{PA}})=64.4$ at $\varepsilon_{\text{PA}}=10^{-10}$ , and compare the six-state threshold $\approx12.6\%$ against Nielsen & Chuang §12.6, Preskill Ch. 4, and Renner's thesis.

Prerequisites. Quantum Bit Error Rate and Sifting · BB84 Protocol · E91 Protocol. Leads to. Decoy-State QKD · Photon-Number-Splitting Attack.

Ask the tutor: Want me to walk through the finite-key length for your own block size, QBER, and target $\varepsilon$ , or to contrast the one-way BB84 threshold with the six-state and two-way advantage-distillation limits?

What is the difference between information reconciliation and privacy amplification?

They solve two problems in sequence. Reconciliation is error correction: Bob's string disagrees with Alice's wherever noise or Eve flipped a bit, so they trade parity information over the public channel until Bob's string exactly equals Alice's. Privacy amplification is secrecy distillation: the now-identical string is still only partly secret — Eve knows something from the quantum channel and everything from the public transcript — so they hash it down to a shorter string across which her residual knowledge is negligible. Reconciliation makes the keys equal; privacy amplification makes them secret — and in that order, because you cannot hash away Eve's knowledge until the two strings are the same.

Why must security use min-entropy instead of the more familiar Shannon entropy?

Because security is about the adversary's best case, not her average case. Shannon entropy $H(X|E)$ measures Eve's uncertainty averaged over all outcomes, but an attacker only needs one good guess. The min-entropy $H_\infty=-\log_2 p_{\text{guess}}$ is minus the log of her single most probable guess, so it measures exactly worst-case unpredictability. A distribution can have large Shannon entropy yet one value that occurs with probability $0.5$ — high average uncertainty, but trivially guessable; hashing it with a length set by Shannon entropy would leave a key Eve can predict half the time. The Leftover Hash Lemma is therefore stated in min-entropy (its smooth version, to handle finite and non-i.i.d. data), and using Shannon entropy in its place is a genuine security bug, not a conservative approximation.

Why does hashing with a random function actually destroy Eve's knowledge?

The key insight is that the randomness protecting the output comes from the public choice of hash, not from the input. A two-universal family guarantees that any two distinct inputs collide under a randomly chosen $g$ with probability at most $2^{-\ell}$ . When you feed in a source with min-entropy $H_\infty$ and hash to $\ell<H_\infty$ bits, this collision bound forces the output distribution — averaged over the hash choice — to be almost perfectly flat, regardless of how the input was shaped. Eve knows which $g$ was used, since it is announced publicly, but that does not help her: the Leftover Hash Lemma bound already accounts for her knowing $g$ . What she cannot do is predict the specific $\ell$ -bit output, because the surplus min-entropy $H_\infty-\ell$ has been spread uniformly across all $2^\ell$ possibilities.

What exactly is reconciliation efficiency, and why does f > 1 cost secret key?

The efficiency factor $f=\text{leak}_{\text{EC}}/[n\,h(Q)]$ compares the bits a real code actually reveals to the Slepian–Wolf minimum $n\,h(Q)$ needed to correct the errors. A perfect code would have $f=1$ ; interactive protocols like Cascade sit around $f\approx1.05$ – $1.2$ because they reveal extra parities during their binary searches, and modern LDPC/polar codes push closer to $1$ . Every bit above the floor is broadcast on the public channel, hence handed to Eve — so the excess $n(f-1)h(Q)$ is subtracted straight from the extractable key length, exactly as in worked example 1. That is why reconciliation efficiency is a first-class figure of merit in QKD data sheets: $f=1.2$ instead of $1.05$ throws away real, otherwise-secret bits and lowers the tolerable error rate.

What changes in the finite-key regime versus the asymptotic rate?

The asymptotic Devetak–Winter rate $r=H(X|E)-H(X|Y)$ assumes infinitely many i.i.d. rounds, so entropies are sharp. Real runs use finite blocks — $10^4$ to $10^9$ bits — where two things intrude. First, the QBER and Eve's information are estimated from a finite sample, so parameter estimation carries a statistical uncertainty $\varepsilon_{\text{PE}}\sim1/\sqrt{n}$ ; you must use a pessimistic confidence bound, not the point estimate. Second, the i.i.d. entropies are replaced by smooth min- and max-entropies, and the extractable length picks up correction terms including the $2\log_2(1/2\varepsilon_{\text{PA}})$ toll of the Leftover Hash Lemma. Together these penalties scale as $\sqrt{n}$ , so short blocks yield disproportionately less key and can give $\ell=0$ even when the asymptotic rate is comfortably positive.

Why must the public discussion channel be authenticated?

Because Eve can not only read the reconciliation and hash-choice messages but potentially modify them. If she impersonates Bob to Alice and Alice to Bob, she runs a man-in-the-middle attack and shares a key with each separately, defeating everything. So each public message carries an information-theoretically secure Wegman–Carter tag, itself built from universal hashing, letting the receiver detect tampering. This consumes a small pre-shared secret key — which is why QKD is technically key expansion, not generation from nothing — but the cost is only logarithmic in the message length, so each run nets far more secret key than it spends.