Metraipolis › archive › dc_0fb71c0eca89

On the Failure Probability of Quantum Leftover Hashing with Bad Seeds — arXiv:2611.03484

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.03484
License (as archived)
CC0-1.0
Archived
2026-11-03T18:51:58.876Z
SHA-256 of the archived text
43a9439b778a7007052d5e94430228ebc9c12b1973305d4573e81a9707d6bff0
Stable URL of this page
https://metraipolis.com/documento/dc_0fb71c0eca89

How to cite

On the Failure Probability of Quantum Leftover Hashing with Bad Seeds — arXiv:2611.03484 — arXiv (en), https://arxiv.org/abs/2611.03484 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0fb71c0eca89 (Metraipolis archive dc_0fb71c0eca89, sha256 43a9439b778a7007052d5e94430228ebc9c12b1973305d4573e81a9707d6bff0)
BibTeX
@misc{dc0fb71c0eca89,
  title = {On the Failure Probability of Quantum Leftover Hashing with Bad Seeds — arXiv:2611.03484},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03484},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0fb71c0eca89; sha256 43a9439b778a7007052d5e94430228ebc9c12b1973305d4573e81a9707d6bff0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03484. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\delta$-close-to-uniform random numbers except with failure probability $\left(\frac{\varepsilon}{\delta}\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}{\delta}\big)^2$. Moreover, we extend the general leftover hash lemma to blockwise hashing and relax the assumption of almost two-universality.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2611.03484 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:15:52.851Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).