arXiv:2611.03484
On the Failure Probability of Quantum Leftover Hashing with Bad Seeds
Asker Friis Bach, Isabel Moreno Babuglia, Jonatan Bohr Brask
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 Summary
The paper studies the probability that a sampled universal-hashing seed gives an output far from uniform against quantum side information, including when the same seed is reused across blocks or sampled imperfectly. The usual leftover hash lemma bounds security averaged over the public seed; here, a seed is called $\delta$-bad when its fixed-seed output has conditional distance from uniform at least $\delta$. For a single extraction, it derives $\Pr[\text{$\delta$-bad}]\leq(\varepsilon/\delta)^2$, where $\varepsilon$ is the specified leftover-hash bound, improving on the direct Markov bound $\varepsilon/\delta$ when $\varepsilon<\delta$. Classical and quantum proofs apply Markov’s inequality to the squared distance and bound its second moment using collision entropy and almost two-universality. The quantum argument additionally uses smoothing and min-entropy–collision-entropy comparisons. For $k$ blocks hashed with one seed, the paper obtains average distance at most $(2k-1)\varepsilon$ and bad-seed probability at most $((2k-1)\varepsilon/\delta)^2$, assuming each block’s min-entropy conditioned on all previous blocks and the adversary is at least the first block’s conditional min-entropy. More general bounds use block-dependent smooth min-entropies. A seed-distribution error $\varepsilon_{\mathrm{seed}}$ adds once to the failure bound, independently of $k$; corresponding average-security statements allow quantum side information about the seed. These guarantees require seed–source independence and additional entropy assumptions for reuse. The paper gives sufficient independence/stationarity conditions and approximate variants, but leaves the weakest conditions permitting the sharper $k\varepsilon$ average-security scaling open.
Central claim may not hold: The abstract's seed-reuse failure bound requires an additional conditional-min-entropy assumption on the source blocks and fails for unrestricted correlated blocks. The detailed single-round quantum theorem has an incorrectly parenthesised logarithm that makes its displayed bound false, although correcting it leaves the intended simplified single-round result standing.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.