Information Reconciliation

After sifting, Alice and Bob hold correlated but not identical raw keys: channel noise and any residual eavesdropping have flipped a fraction $Q$ (the QBER) of their bits. Before they can use the key they must make their strings agree exactly, while leaking as little as possible to Eve, who listens to all the public discussion. This is information reconciliation — classical error correction over a public channel, run with one eye on the leakage budget.

The problem, information-theoretically

Model Alice's key $X$ and Bob's key $Y$ as related by a binary symmetric channel with crossover probability $Q$ : each bit independently disagrees with probability $Q$ . Bob's residual uncertainty about Alice's string, per bit, is the binary entropy

H(X \mid Y) = h(Q), \qquad h(Q) = -Q\log_2 Q - (1-Q)\log_2(1-Q).

Shannon's noiseless-coding/source-coding bound says Bob needs at least $h(Q)$ bits of side information per key bit from Alice to reconstruct $X$ with vanishing error. So reconciliation must reveal something publicly — there is an unavoidable cost.

\text{leakage} \ \ge\ n\, h(Q) \quad \text{bits, for an $n$-bit key.}

A practical scheme leaks $\text{leak}_{\mathrm{EC}} = f_{\mathrm{EC}}\, n\, h(Q)$ with an efficiency factor $f_{\mathrm{EC}} \ge 1$ (ideal $=1$ ; real codes $\approx 1.05$ – $1.2$ ).

Cascade: reconciliation by public parity discussion

The classic interactive protocol is Cascade (Brassard–Salvail, 1993):

Alice and Bob agree on a random permutation and split their keys into blocks of size $\sim 0.73/Q$ .
For each block they exchange parities (the XOR of the block's bits). A parity mismatch means an odd number of errors in that block.
They binary-search the mismatched block: split it in half, compare parities, recurse into the half whose parity disagrees. After $\lceil\log_2(\text{block size})\rceil$ rounds they pinpoint and flip exactly one erroneous bit.
They reshuffle with a new permutation and repeat over several passes. Because a fixed bit lands in different blocks each pass, errors that hid behind even-parity cancellations in one pass get exposed and corrected in the next — the corrections cascade.

Every revealed parity is public, so Eve learns one bit of information per parity exchanged. The total parity traffic is what the efficiency $f_{\mathrm{EC}}$ measures.

Accounting for the leakage

Every public bit exchanged is potential information for Eve and must be subtracted from the final key length. After reconciliation Alice and Bob share an identical string $X$ , but its secrecy has been degraded by both the original quantum leakage (bounded by $Q$ ) and the reconciliation leakage $\text{leak}_{\mathrm{EC}}$ . The net extractable secret-key length follows the schematic Devetak–Winter form, here for one-way reconciliation:

\ell \ \approx\ n\big[\,1 - h(Q) - \chi(Q)\,\big] \ -\ \underbrace{(f_{\mathrm{EC}}-1)\,n\,h(Q)}_{\text{inefficiency penalty}},

where the $h(Q)$ term is the ideal reconciliation cost, $\chi(Q)$ bounds Eve's quantum side information, and the last term is the price of imperfect codes. The remaining secrecy gap is closed in the next lesson by privacy amplification.

Verification: did it actually work?

Cascade and LDPC correct most errors but can fail silently. So reconciliation ends with an error-verification step: Alice and Bob compute a short hash (e.g. a few-bit universal hash) of their corrected keys and compare it publicly. If the hashes match, the keys are equal except with probability $\sim 2^{-t}$ for a $t$ -bit hash; if not, they abort or run another pass. Only then do they hold a genuinely identical raw key — noisy in secrecy, but bit-for-bit reconciled — ready for privacy amplification.