Privacy Amplification

After reconciliation, Alice and Bob share an identical $n$ -bit string — but Eve holds partial information about it from both the quantum channel and the public reconciliation traffic. Privacy amplification is the final distillation: compress the partly-compromised string into a shorter key about which Eve is left almost perfectly ignorant. Remarkably, this is possible even though Alice and Bob do not know which bits Eve knows.

The right measure: min-entropy

Shannon entropy measures average uncertainty, but security needs a worst-case guarantee. The correct quantity is the conditional min-entropy $H_{\min}(X \mid E)$ , governed by Eve's best single guess:

H_{\min}(X \mid E) = -\log_2 p_{\text{guess}}(X \mid E),

where $p_{\text{guess}}$ is the probability Eve correctly guesses $X$ using her optimal strategy on her quantum side information $E$ . A large min-entropy means even Eve's best guess is unlikely to be right. This is the resource privacy amplification spends.

Universal hashing and the Leftover Hash Lemma

The tool is a 2-universal family of hash functions $\{f_s : \{0,1\}^n \to \{0,1\}^\ell\}$ — a set such that for $x \neq x'$ and a randomly chosen $s$ ,

\Pr_s[f_s(x) = f_s(x')] \le 2^{-\ell}.

Alice picks $s$ publicly at random, both apply $K = f_s(X)$ , and the $\ell$ -bit output $K$ is the final key. The Leftover Hash Lemma (the quantum version is due to Renner) quantifies how secret $K$ is: if $\ell$ is chosen below Eve's min-entropy, the output is nearly uniform and nearly independent of Eve, measured in trace distance,

\big\| \rho_{KE} - \tau_K \otimes \rho_E \big\|_1 \ \le\ \tfrac12\, 2^{-\tfrac12\,(H_{\min}(X\mid E) - \ell)},

where $\tau_K = 2^{-\ell}\mathbb{1}$ is the perfectly uniform key. The bound shrinks exponentially as the security parameter $H_{\min}(X\mid E) - \ell$ grows.

Choosing the output length

To make the key $\varepsilon$ -secret (trace distance $\le \varepsilon$ ), set the extractable length to roughly the smooth min-entropy minus a security margin:

\ell \ \approx\ H_{\min}^{\varepsilon}(X \mid E) \ -\ 2\log_2\tfrac{1}{\varepsilon}.

Subtracting reconciliation leakage too (each public parity reduces Eve's uncertainty), a standard finite-key statement reads

\ell \ \approx\ H_{\min}^{\varepsilon}(X \mid E) \ -\ \text{leak}_{\mathrm{EC}} \ -\ 2\log_2\tfrac{1}{\varepsilon}.

Asymptotically, $H_{\min}/n$ tends to $1 - \chi$ where $\chi$ is Eve's Holevo information per bit, so the surviving secret fraction is the Devetak–Winter rate met earlier. Privacy amplification is what makes that rate operational: it physically realizes the distillation.

Why min-entropy, not Shannon entropy

Suppose Eve is certain of half the bits and ignorant of the other half. The Shannon entropy is $n/2$ , but if the "ignorant" half were structured she might still guess well; min-entropy captures the true worst case and cannot be inflated by such structure. Using Shannon entropy here would over-estimate the extractable length and break security. The migration from average- to worst-case entropies — and their smooth variants for finite samples — is the technical core of modern QKD security proofs (Renner).

The complete BB84 pipeline

Putting the module together, a full QKD run is: distribute quantum signals → sift matching bases ( $\to n/2$ bits) → estimate the QBER on a public sample (abort if too high) → reconcile to an identical string (leaking $\text{leak}_{\mathrm{EC}}$ ) → privacy-amplify by universal hashing down to $\ell$ bits → authenticate all classical messages (to stop active man-in-the-middle attacks). The output is a key that is $\varepsilon$ -close to uniform and independent of everything Eve could possibly hold — ready to feed a one-time pad.