One Key Good, L Keys Better: List Decoding Meets Quantum Privacy Amplification

• URL: http://arxiv.org/abs/2603.18097v1
• Date: Wed, 18 Mar 2026 10:37:05 GMT
• Title: One Key Good, L Keys Better: List Decoding Meets Quantum Privacy Amplification
• Abstract summary: List privacy amplification (LPA)<n>We formalise LPA and prove the emphQuantum List Leftover Hash Lemma (QLLHL)
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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/ε) - 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^{αn'}$ increases the tolerable phase-error threshold from $h^{-1}(1 - h(e_b))$ to $h^{-1}(1 - h(e_b) + α)$, exceeding the standard $\approx 11\%$ bound for any $α> 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.

Related papers

• Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
  We introduce ordered-angle coding for binary-unanimity testing among $n$ transformation-only users in a serial quantum architecture.<n>Bell entanglement is not required for the additive algebra, but it keeps the traveler locally maximally mixed in every honest trial.
  arXiv  Detail & Related papers  (2026-09-04T18:28:01Z)
• A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes [2.1485350418225244]
  A pseudorandom code (PRC) is a keyed error-correcting code whose codewords are computationally indistinguishable from uniform strings.<n>We study publickey PRCs over fixed alphabets against adversarial deletions.
  arXiv  Detail & Related papers  (2026-08-31T21:31:03Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• Towards Worst-case Hardness for Low-Noise LPN [6.6603865098703805]
  Existing worst-case-to-average-case reductions for [BLVW19, YZ21] rely on statistical smoothing of linear codes.<n>We show that any efficient solver can be transformed into a pair of efficient algorithms.
  arXiv  Detail & Related papers  (2026-06-04T08:11:23Z)
• Quantum Sketches, Hashing, and Approximate Nearest Neighbors [0.0]
  In a broad quantum sketch model, the dataset $P$ is encoded as an $m$-qubit state $_P$, and each query is answered by an arbitrary query-dependent measurement on a fresh copy of $_P$.<n>For every approximation factor $cge 1$ and constant success probability $p>1/2$, we exhibit $n$-point instances in Hamming space $0,1d$ with $d=(log n)$ for which any such sketch requires $m=(n)$ qubits.
  arXiv  Detail & Related papers  (2026-02-22T16:18:36Z)
• Super-Quadratic Quantum Speed-ups and Guessing Many Likely Keys [43.5605535402594]
  We study the fundamental problem of guessing cryptographic keys.<n>We find that in a multi-key setting the guessing cost per key is substantially smaller than in a single-key setting.
  arXiv  Detail & Related papers  (2025-09-08T11:03:49Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  We give a conceptually simple quantum linear system solvers (QLSS) that does not use complex or difficult-to-analyze techniques. If the solution norm $lVertboldsymbolxrVert$ is known exactly, our QLSS requires only a single application of kernel. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(kappa)$ complexity can be achieved for norm estimation.
  arXiv  Detail & Related papers  (2024-06-17T20:54:11Z)
• Efficient Quantum State Preparation with Walsh Series [0.0]
  A new approximate Quantum State Preparation (QSP) method is introduced, called the Walsh Series Loader (WSL) WSL approximates quantum states defined by real-valued functions of single real variables with a depth independent of the number $n$ of qubits.
  arXiv  Detail & Related papers  (2023-07-17T10:44:28Z)
• Tokenization and the Noiseless Channel [71.25796813073399]
  Good tokenizers lead to emphefficient channel usage, where the channel is the means by which some input is conveyed to the model. In machine translation, we find that across multiple tokenizers, the R'enyi entropy with $alpha = 2.5$ has a very strong correlation with textscBleu: $0.78$ in comparison to just $-0.32$ for compressed length.
  arXiv  Detail & Related papers  (2023-06-29T10:32:09Z)
• Invertible Bloom Lookup Tables with Less Memory and Randomness [23.724300017513574]
  Invertible Bloom Lookup Tables (IBLTs) have found applications in set reconciliation protocols, error-correcting codes, and the design of advanced cryptographic primitives.<n>We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness.<n>We show that hashing $n$ keys with any $k$-wise independent hash function $h:U to [Cn]$ for some sufficiently large constant $C$ guarantees with probability $1 - 2-Omega(k)$ that at least $n/2$ keys will have a unique hash value
  arXiv  Detail & Related papers  (2023-06-13T07:15:02Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.