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.