On the Failure Probability of Quantum Leftover Hashing with Bad Seeds

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 ε 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 (ε/δ)². This result is generalised to blockwise hashing providing a guarantee of the security of k rounds except with failure probability (((2k−1)ε)/δ)². Moreover, we extend the general leftover hash lemma to blockwise hashing and relax the assumption of almost two-universality.

Spatially Coupled MacKay-Neal/Hsu-Anastasopoulos CSS Codes Achieve the Quantum-Erasure Hashing Bound by Seeded BP Decoding
Kenta Kasai
arXiv13 Sep 2026PreprintarXiv licenceFull textGeneral mathematics Quantum physics & quantum informationarXiv
Deformed W-algebras and chiralized cluster seeds: subregular W-algebras and Inverse Quantum Hamiltonian Reduction
Mikhail Bershtein, Jean-Emile Bourgine, Ethan Fursman
arXiv2 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Mathematical physicsarXiv
The Pauli Probability Spectrum Carries the Pure-State Quantum Fisher Metric
E. A. Ramirez Trino, M. A. Rajabpour
arXiv17 Sep 2026PreprintarXiv licenceFull textMathematical physics Quantum physics & quantum informationarXiv
On the applicability of Kolmogorov's theory of probability to the description of quantum phenomena. Part II: Bell inequalities
Maik Reddiger
arXiv25 Sep 2026PreprintarXiv licenceFull textMathematical physics Quantum physics & quantum informationarXiv
Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes
Avijit Mandal, Christophe Piveteau, Joseph M. Renes +1
arXiv5 Oct 2026PreprintCC BY 4.0Full textGeneral mathematics Quantum physics & quantum informationarXiv

Cite

BibTeX RIS

BibTeX

@misc{bach2026failure,
  title = {{On the Failure Probability of Quantum Leftover Hashing with Bad Seeds}},
  author = {Asker Friis Bach and Isabel Moreno Babuglia and Jonatan Bohr Brask},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.03484},
  eprint = {2611.03484},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03484},
}

RIS

TY  - UNPB
TI  - On the Failure Probability of Quantum Leftover Hashing with Bad Seeds
AU  - Asker Friis Bach
AU  - Isabel Moreno Babuglia
AU  - Jonatan Bohr Brask
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.03484
UR  - https://arxiv.org/abs/2611.03484
AB  - 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 ε 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 (ε/δ)^2. This result is generalised to blockwise hashing providing a guarantee of the security of k rounds except with failure probability (((2k−1)ε)/δ)^2. Moreover, we extend the general leftover hash lemma to blockwise hashing and relax the assumption of almost two-universality.
ER  -

Abstract

Related

Cite