On the Failure Probability of Quantum Leftover Hashing with Bad Seeds

Asker Friis Bach, Isabel Moreno Babuglia, Jonatan Bohr Brask

Nov 2, 2026arXiv:2611.03484v1

quant-phcs.IT

Scorecard· 15/16

5.0/10 impact

Correct and practically motivated refinement of the quantum leftover hash lemma for seed reuse, but built mostly from existing tools and limited by a strong block-entropy assumption.

Abstract

We study hashing against quantum adversaries, as used in cryptographic applications, and provide bounds on the probability of failure in practical settings where seeds might be reused and might be non-ideal. Randomness extraction and privacy amplification are key components of quantum cryptographic protocols, such as quantum randomness generation or key distribution, that allow the compression of partially secure raw data into shorter output with high security. To ensure the security of any cryptographic construction that integrates them, it is desirable to establish composable security. This can be done by using methods based on universal hashing and leveraging the general leftover hash lemma, which allows extraction of near-uniform random numbers from an imperfect entropy source by sampling from an almost two-universal family of hash functions using a seed. This approach is taken in many practical implementations, commonly using Toeplitz hashing. The lemma provides an upper bound $\varepsilon$ on the distance of the output to uniform randomness, which holds on average over the choice of seeds. It makes no claim that any particular seed yields near-uniform random numbers. This poses a problem for practical applications where a seed is sampled once and reused for many rounds (blockwise hashing). Here, we study the subset of \textit{bad} seeds yielding far-from-uniform outputs. We show that randomness extraction against quantum side information is guaranteed to produce $δ$ -close-to-uniform random numbers except with failure probability $\left(\frac{\varepsilon}δ\right)^2$ . This result is generalised to blockwise hashing providing a guarantee of the security of $k$ rounds except with failure probability $\big(\frac{(2k-1)\varepsilon}δ\big)^2$ . Moreover, we extend the general leftover hash lemma to blockwise hashing and relax the assumption of almost two-universality.

AI Impact Assessments

(1 model)

1. Core Contribution

The paper addresses a gap in how the quantum leftover hash lemma (LHL) is used in practice. The LHL (Tomamichel et al.) bounds the distance to uniform only on average over seeds. QRNG and QKD implementations often draw one Toeplitz seed and reuse it across many blocks, and the Toeplitz zero matrix is an extreme example of a bad seed. The authors define δ-bad seeds, those whose output is at least δ-far from uniform given quantum side information E. They then bound the probability of drawing one.

Single round. Instead of the linear Markov bound ε/δ, they apply Markov to the squared distance and bound its expectation via conditional collision entropy. Pr[bad] ≤ (ε/δ)², with a tighter collision-entropy form in the classical case. In the quantum case the proof reuses Lemmas 3 and 4 of Tomamichel et al. and adds an averaged collision-entropy-under-hashing lemma (Lemma III.16). Only a fraction ε of seeds are √ε-bad.

Blockwise hashing. They extend the LHL to k blocks with a reused seed, giving security parameter (2k−1)ε. This needs assumption (A): the smooth min-entropy of each new block given all past blocks is at least that of the first block. They show (A) follows from conditional independence plus marginal stationarity, with penalties for approximate versions via Fawzi–Renner recovery maps. Under i.i.d. assumptions the bound sharpens to kε. The failure probability is ((2k−1)ε/δ)². The factor 2k−1 comes from a Cauchy–Schwarz step over telescoping hybrids, and the 2 from Lemma IV.12.

Imperfect seeds. If the seed is only ε_seed-close to a µ-U₂ distribution, even with quantum side information on the seed, the penalty is an additive ε_seed. It is paid once, independent of k.

2. Methodological Rigor

The proofs are elementary but appear correct. The squared-Markov step, Jensen, Cauchy–Schwarz with the weight vector (1, √2, …, √2), and the hybrid-argument telescoping are all standard and cleanly executed. The treatment of the quantum minimum over σ_E (Remark III.6, Appendix A) is careful. There are no experiments, which is appropriate for a theory paper.

Substantive concerns:

Assumption (A) is not a mild technicality. It essentially requires stationary, conditionally independent block generation. Real devices with drift, memory, or adversarial correlations can violate it. The authors admit they do not know the weakest sufficient assumption.

The "quadratic improvement" is a modest technical observation. It exploits the second moment already implicit in the LHL proof, via collision entropy. Stinson had a related classical quadratic result. Because ε is typically ~2⁻⁶⁴ or smaller, the improvement matters less in practice than in principle.

The Lemma IV.12 factor of 2 loosens the blockwise bound relative to the classical case.

The seed-relaxation result (additive ε_seed) is a nearly immediate consequence of the total-variation property, and its novelty is small.

3. Potential Impact

The result gives a rigorous, citable statement for practitioners: "except with probability ((2k−1)ε/δ)², a publicly known reused seed yields δ-close-to-uniform output." This closes a conceptual gap in many published QRNG and QKD post-processing pipelines that reuse Toeplitz seeds (e.g., Gehring et al., Bruynsteen et al.). It also gives a composable accounting for seeds produced by another extractor. It could be cited in security proofs and certification documents for QRNG products. It will not change the direction of quantum cryptography theory. It is a tidy refinement for a narrow but real community: quantum randomness extraction, QRNG engineering, and privacy amplification in QKD.

4. Timeliness & Relevance

Commercial QRNG and high-rate QKD post-processing (Gbps FPGA Toeplitz extractors) are maturing, and certification pressure makes seed-reuse security a live concern. The paper is timely for this engineering-facing niche, and the Danish QRNG industry context is visible in the authorship. The topic is not a major open bottleneck in the field.

5. Strengths & Limitations

Strengths:

It clearly states and answers three well-motivated practical questions (Q1–Q3).

It treats quantum side information properly, including a fixed-seed channel formalism that makes bad seeds well defined.

The three-tier assumption hierarchy (A) ⇐ CI+MS ⇐ I+S, with quantified penalties, is useful.

The additive-once ε_seed result is practically relevant for self-bootstrapped seeds.

Limitations:

The contribution is largely a combination of existing tools (Tomamichel et al. lemmas, Markov/Jensen, Fawzi–Renner).

Assumption (A) limits applicability to realistic correlated sources.

No numerical illustration or worked example shows how the bound compares quantitatively to the linear Markov bound or to Toeplitz-specific analysis. No concrete QRNG parameter instantiation is given.

It does not address the more serious scenario of seed reuse where earlier outputs leak to the adversary, beyond what is folded into the side information.

Some presentational glitches in the PDF text (garbled fractions, date artifacts) and heavy notation.

Overall this is a competent, correct, useful but incremental theory paper with a moderately sized audience.

Rating:5/ 10

Significance 4.5Rigor 7Novelty 4.5Clarity 6.5

Generated Nov 3, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 15/16

5.0/10 impact

Correct and practically motivated refinement of the quantum leftover hash lemma for seed reuse, but built mostly from existing tools and limited by a strong block-entropy assumption.