Search papers, labs, and topics across Lattice.
This paper introduces List Privacy Amplification (LPA), a novel relaxation of quantum key distribution (QKD) that extracts a list of L candidate keys, guaranteeing at least one is perfectly secret from an eavesdropper. They formalize LPA within the abstract cryptography framework and prove the Quantum List Leftover Hash Lemma (QLLHL), demonstrating a tight additive log L gain over the standard QLHL in achievable key length. Applying QLLHL to BB84-type QKD, the tolerable phase-error threshold is increased, exceeding the standard ~11% bound.
Tolerable error rates in quantum key distribution just got a whole lot better: extracting a *list* of candidate keys, instead of a single one, allows for provably secure key exchange even with higher levels of noise.
We introduce list privacy amplification (LPA), a relaxation of the final step of quantum key distribution (QKD) in which Alice and Bob extract a list of $L$ candidate keys from a raw string correlated with an eavesdropper Eve, with the guarantee that at least one key is perfectly secret while Eve cannot identify which. This parallels list decoding in error-correcting codes: relaxing unique decoding to list decoding increases the decoding radius; analogously, list extraction increases achievable key length beyond the standard quantum leftover hash lemma (QLHL). Within the abstract cryptography framework, we formalise LPA and prove the \emph{Quantum List Leftover Hash Lemma} (QLLHL): an $L$-list of $\ell$-bit keys can be extracted from an $n$-bit source with smooth min-entropy $k$ iff \[ \ell \le k + \log L - 2\log(1/\epsilon) - 3, \] yielding a tight additive $\log L$ gain over QLHL. This gain arises because the index of the secure key is chosen after hashing and hidden from Eve, effectively contributing $\log L$ bits of entropy. Applying QLLHL to BB84-type QKD, a list size $L = 2^{\alpha n'}$ increases the tolerable phase-error threshold from $h^{-1}(1 - h(e_b))$ to $h^{-1}(1 - h(e_b) + \alpha)$, exceeding the standard $\approx 11\%$ bound for any $\alpha>0$. We prove tightness via a matching intercept-resend attack, establish composability with Wegman--Carter authentication, and present two constructions: a polynomial inner-product hash over $\mathbb{F}_{2^m}$ and a Toeplitz-based variant, running in $O(nL)$ and $O(nL \log n)$ time.
