Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1002.2436 · IEEE Transactions on Information Theory

Leftover Hashing Against Quantum Side Information

Marco Tomamichel, Christian Schaffner, Adam Smith, Renato Renner

Published Aug 1, 2011• 339 citations
arXivHTMLPDF

Abstract

The Leftover Hash Lemma states that the output of a two-universal hash function applied to an input with sufficiently high entropy is almost uniformly random. In its standard formulation, the lemma refers to a notion of randomness that is (usually implicitly) defined with respect to classical side information. Here, a strictly more general version of the Leftover Hash Lemma that is valid even if side information is represented by the state of a quantum system is shown. Our result applies to almost two-universal families of hash functions. The generalized Leftover Hash Lemma has applications in cryptography, e.g., for key agreement in the presence of an adversary who is not restricted to classical information processing.

DOI
10.1109/tit.2011.2158473

Related papers

Leftover Hashing against quantum side information

Marco Tomamichel, Renato Renner, Christian Schaffner +1 more

The Leftover Hash Lemma states that the output of a two-universal hash function applied to an input with sufficiently high entropy is almost uniformly random. In its standard formulation, the lemma refers to a notion of randomness that is (usually implicitly) defined with respect to classical side information. Here, we prove a (strictly) more general version of the Leftover Hash Lemma that is valid even if side information is represented by the state of a quantum system. Furthermore, our result applies to arbitrary δ-almost two-universal families of hash functions. The generalized Leftover Hash Lemma has applications in cryptography, e.g., for key agreement in the presence of an adversary who is not restricted to classical information processing.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•48 citations

On the Failure Probability of Quantum Leftover Hashing with Bad Seeds

Asker Friis Bach, Isabel Moreno Babuglia, Jonatan Bohr Brask

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.

quant-pharXiv:2611.03484•Nov 3, 2026•0 citations

Extracting classical randomness in a quantum world

Renato Renner

Extractors are functions that transform a weakly random value X into an almost perfectly uniform value Z. Traditionally, extractors have been studied in a context where the side information, relative to which the distributions of X and Z are defined, is purely classical. Only recently, the notion of extractors has been generalized to scenarios where side information might be represented by the state of a quantum-mechanical system (while X and Z are still classical). This generalization is crucial for numerous applications, e.g., in cryptography, where an adversary might hold quantum-mechanical side information. In this article, we review this generalized notion of extractors as well as a construction of extractors based on two-universal hashing.

IEEE Information Theory Workshop (ITW)•May 1, 2008•2 citations

Dual Universality of Hash Functions and Its Applications to Quantum Cryptography

Toyohiro Tsurumaru, M. Hayashi

In this paper, we introduce the concept of dual universality of hash functions and present its applications to quantum cryptography. We begin by establishing the one-to-one correspondence between a linear function familyFand a code familyC, and thereby defining ε-almost dual universal2hash functions, as a generalization of the conventional universal2hash functions. Then, we show that this generalized (and thus broader) class of hash functions is in fact sufficient for the security of quantum cryptography. This result can be explained in two different formalisms. First, by noting its relation to the δ-biased family introduced by Dodis and Smith, we demonstrate that Renner's two-universal hashing lemma is generalized to our class of hash functions. Next, we prove that the proof technique by Shor and Preskill can be applied to quantum key distribution (QKD) systems that use our generalized class of hash functions for privacy amplification. While Shor-Preskill formalism requires an implementer of a QKD system to explicitly construct a linear code of the Calderbank-Shor-Steane (CSS) type, this result removes the existing difficulty of the construction of a linear code of CSS code by replacing it by the combination of an ordinary classical error correcting code and our proposed hash function. We also show that a similar result applies to the quantum wire-tap channel. Finally, we compare our results in the two formalisms and show that, in typical QKD scenarios, the Shor-Preskill-type argument gives better security bounds in terms of the trace distance and Holevo information than the method based on the δ-biased family.

arXiv:1101.0064•IEEE Transactions on Information Theory•Apr 2, 2013•58 citations

Sharp lower bounds on the extractable randomness from non-uniform sources

Boris Škorić, Chibuzo Obi, Evgeny A. Verbitskiy +1 more

Extraction of uniform randomness from (noisy) non-uniform sources is an important primitive in many security applications, e.g. (pseudo-)random number generators, privacy-preserving biometrics, and key storage based on Physical Unclonable Functions. Generic extraction methods exist, using universal hash functions. There is a trade-off between the length of the extracted bit string and the uniformity of the string. In the literature there are proven lower bounds on this length as a function of the desired uniformity. The best known bound involves a quantity known as smooth min-entropy. Unfortunately, there exist at least three definitions of smooth entropy. In this paper we compare three of these definitions, and we derive improved lower bounds on the extractable randomness.\nWe also investigate the use of almost universal hash functions, which are slightly worse at extracting randomness than universal hash functions, but are preferable in practice because they require far less resources in devices. We show that using them has negligible effect on the extractable randomness.\nKeywords: Leftover Hash Lemma; Universal hash function; Randomness extraction

•Jan 1, 2008•0 citations

Generalised entropy accumulation

Tony Metger, Omar Fawzi, David Sutter +1 more

The min-entropy of a quantum system A conditioned on another quantum system E describes how much randomness can be extracted from A with respect to an adversary in possession of E. This quantity plays a crucial role in quantum cryptography: the security proofs of many quantum cryptographic protocols reduce to showing a lower bound on such a min-entropy. Here, we develop a new tool, called generalised entropy accumulation, for computing such bounds. Concretely, we consider a sequential process in which each step outputs a system Aiand updates a side information register E. We prove that if this process satisfies a natural “non-signalling” condition between past outputs and future side information, the min-entropy of the outputs $A_{1},\ldots,\ A_{n}$ conditioned on the side information E at the end of the process can be bounded from below by a sum of von Neumann entropies associated with the individual steps. This is a generalisation of the entropy accumulation theorem (EAT) [1], which deals with a more restrictive model of side information: there, past side information cannot be updated in subsequent rounds, and newly generated side information has to satisfy a Markov condition.Due to its more general model of side-information, our generalised EAT can be applied more easily and to a broader range of cryptographic protocols. In particular, it is the first general tool that is applicable to mistrustful device-independent cryptography. To demonstrate this, we give the first security proof for blind randomness expansion [2] against general adversaries. Furthermore, our generalised EAT can be used to give improved security proofs for quantum key distribution [3], and also has applications beyond quantum cryptography.

Annual Symposium on Foundations of Computer Science•Oct 1, 2022•46 citations
The Leftover Hash Lemma states that the output of a two-universal hash function applied to an input with sufficiently high entropy is almost uniformly random. In its standard formulation, the lemma refers to a notion of randomness that is (usually implicitly) defined with respect to classical side information. Here, a strictly more general version of the Leftover Hash Lemma that is valid even if side information is represented by the state of a quantum system is shown. Our result applies to almost two-universal families of hash functions. The generalized Leftover Hash Lemma has applications in cryptography, e.g., for key agreement in the presence of an adversary who is not restricted to classical information processing.
The Leftover Hash Lemma states that the output of a two-universal hash function applied to an input with sufficiently high entropy is almost uniformly random. In its standard formulation, the lemma refers to a notion of randomness that is (usually implicitly) defined with respect to classical side information. Here, we prove a (strictly) more general version of the Leftover Hash Lemma that is valid even if side information is represented by the state of a quantum system. Furthermore, our result applies to arbitrary δ-almost two-universal families of hash functions. The generalized Leftover Hash Lemma has applications in cryptography, e.g., for key agreement in the presence of an adversary who is not restricted to classical information processing.
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 (εδ)2\left(\frac{\varepsilon}δ\right)^2(δε​)2. This result is generalised to blockwise hashing providing a guarantee of the security of kkk rounds except with failure probability ((2k−1)εδ)2\big(\frac{(2k-1)\varepsilon}δ\big)^2(δ(2k−1)ε​)2. Moreover, we extend the general leftover hash lemma to blockwise hashing and relax the assumption of almost two-universality.
Extractors are functions that transform a weakly random value X into an almost perfectly uniform value Z. Traditionally, extractors have been studied in a context where the side information, relative to which the distributions of X and Z are defined, is purely classical. Only recently, the notion of extractors has been generalized to scenarios where side information might be represented by the state of a quantum-mechanical system (while X and Z are still classical). This generalization is crucial for numerous applications, e.g., in cryptography, where an adversary might hold quantum-mechanical side information. In this article, we review this generalized notion of extractors as well as a construction of extractors based on two-universal hashing.
In this paper, we introduce the concept of dual universality of hash functions and present its applications to quantum cryptography. We begin by establishing the one-to-one correspondence between a linear function familyFand a code familyC, and thereby defining ε-almost dual universal2hash functions, as a generalization of the conventional universal2hash functions. Then, we show that this generalized (and thus broader) class of hash functions is in fact sufficient for the security of quantum cryptography. This result can be explained in two different formalisms. First, by noting its relation to the δ-biased family introduced by Dodis and Smith, we demonstrate that Renner's two-universal hashing lemma is generalized to our class of hash functions. Next, we prove that the proof technique by Shor and Preskill can be applied to quantum key distribution (QKD) systems that use our generalized class of hash functions for privacy amplification. While Shor-Preskill formalism requires an implementer of a QKD system to explicitly construct a linear code of the Calderbank-Shor-Steane (CSS) type, this result removes the existing difficulty of the construction of a linear code of CSS code by replacing it by the combination of an ordinary classical error correcting code and our proposed hash function. We also show that a similar result applies to the quantum wire-tap channel. Finally, we compare our results in the two formalisms and show that, in typical QKD scenarios, the Shor-Preskill-type argument gives better security bounds in terms of the trace distance and Holevo information than the method based on the δ-biased family.
Extraction of uniform randomness from (noisy) non-uniform sources is an important primitive in many security applications, e.g. (pseudo-)random number generators, privacy-preserving biometrics, and key storage based on Physical Unclonable Functions. Generic extraction methods exist, using universal hash functions. There is a trade-off between the length of the extracted bit string and the uniformity of the string. In the literature there are proven lower bounds on this length as a function of the desired uniformity. The best known bound involves a quantity known as smooth min-entropy. Unfortunately, there exist at least three definitions of smooth entropy. In this paper we compare three of these definitions, and we derive improved lower bounds on the extractable randomness.\nWe also investigate the use of almost universal hash functions, which are slightly worse at extracting randomness than universal hash functions, but are preferable in practice because they require far less resources in devices. We show that using them has negligible effect on the extractable randomness.\nKeywords: Leftover Hash Lemma; Universal hash function; Randomness extraction
The min-entropy of a quantum system A conditioned on another quantum system E describes how much randomness can be extracted from A with respect to an adversary in possession of E. This quantity plays a crucial role in quantum cryptography: the security proofs of many quantum cryptographic protocols reduce to showing a lower bound on such a min-entropy. Here, we develop a new tool, called generalised entropy accumulation, for computing such bounds. Concretely, we consider a sequential process in which each step outputs a system Aiand updates a side information register E. We prove that if this process satisfies a natural “non-signalling” condition between past outputs and future side information, the min-entropy of the outputs A1,…, AnA_{1},\ldots,\ A_{n}A1​,…, An​ conditioned on the side information E at the end of the process can be bounded from below by a sum of von Neumann entropies associated with the individual steps. This is a generalisation of the entropy accumulation theorem (EAT) [1], which deals with a more restrictive model of side information: there, past side information cannot be updated in subsequent rounds, and newly generated side information has to satisfy a Markov condition.Due to its more general model of side-information, our generalised EAT can be applied more easily and to a broader range of cryptographic protocols. In particular, it is the first general tool that is applicable to mistrustful device-independent cryptography. To demonstrate this, we give the first security proof for blind randomness expansion [2] against general adversaries. Furthermore, our generalised EAT can be used to give improved security proofs for quantum key distribution [3], and also has applications beyond quantum cryptography.