In quantum key distribution, privacy amplification distills a short, secure key from a longer, partially compromised string. The standard quantum leftover hash lemma gives the maximum key length extractable from a string with a given min-entropy against a quantum adversary. Exceed this length and the key is insecure.
This paper relaxes the problem: instead of extracting one key, extract a list of L candidate keys, one of which is guaranteed secure. The Quantum List Leftover Hash Lemma proves that this costs only log L fewer bits of security — an additive, not multiplicative, penalty. The gain is dramatic: by tolerating a short list of candidates (which the legitimate parties can narrow down using a small additional authenticated exchange), the tolerable error threshold in BB84-type protocols exceeds the conventional ~11% phase-error bound.
The construction is efficient. Two hash-based schemes achieve the bound: one using universal hash families, another using two-universal hash families with an additional linear code. Both run in polynomial time. The bounds are tight — matching converse results prove that the additive log L gain is optimal.
The idea imports list decoding from classical coding theory into quantum cryptography. In list decoding, a received word is decoded to a short list of possible messages rather than a single message, enabling recovery from more errors than unique decoding allows. The same trade-off applies to privacy amplification: accepting ambiguity in which key is the real one buys tolerance to more noise, which translates directly to higher error thresholds.
Correction (2026-11-06): I checked this essay against the raw arXiv abstract of Kulkarni, 'One Key Good, L Keys Better: List Decoding Meets Quantum Privacy Amplification' (2603.18097, v1). The Quantum List Leftover Hash Lemma gives a tight additive gain of log L in the extractable key length (an L-list of l-bit keys can be extracted iff l is at most k + log L - 2 log(1/epsilon) - 3); I wrote that the list costs 'log L fewer bits of security', a penalty, which has the sign backwards. The list size behind the improved threshold is exponential, L = 2^(alpha n'), which raises the tolerable phase-error threshold above the standard 11 percent for any alpha greater than 0; I called it a 'short list'. The guarantee is that at least one key is perfectly secret and Eve cannot identify which, because the index is chosen after hashing. The two constructions in the abstract are a polynomial inner-product hash over F_(2^m) and a Toeplitz-based variant, running in O(nL) and O(nL log n) time, not the pair of hash schemes I described, and the narrowing of the list by a small authenticated exchange is not in the abstract. I checked the abstract and author list only.