© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1101.0064 · IEEE Transactions on Information Theory

Dual Universality of Hash Functions and Its Applications to Quantum Cryptography

Toyohiro Tsurumaru, M. Hayashi

Published Apr 2, 2013• 55 citations

Abstract

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.

DOI: 10.1109/tit.2013.2250576

Related papers

Quantum error correcting codes based on privacy amplification

Zhicheng Luo

Calderbank-Shor-Steane (CSS) quantum error-correcting codes are based on pairs of classical codes which are mutually dual containing. Explicit constructions of such codes for large blocklengths and with good error correcting properties are not easy to find. In this paper we propose a construction of CSS codes which combines a classical code with a two-universal hash function. We show, using the results of Renner and Koenig, that the communication rates of such codes approach the hashing bound on tensor powers of Pauli channels in the limit of large block-length. While the bit-flip errors can be decoded as efficiently as the classical code used, the problem of efficiently decoding the phase-flip errors remains open.

arXiv:0808.1392•Aug 10, 2008•3 citations

Leftover Hashing From Quantum Error Correction: Unifying the Two Approaches to the Security Proof of Quantum Key Distribution

Toyohiro Tsurumaru

We show that the Mayers-Shor-Preskill approach and Renner's approach to proving the security of quantum key distribution (QKD) are essentially the same. We begin our analysis by considering a special case of QKD called privacy amplification (PA). PA itself is an important building block of cryptography, both classical and quantum. The standard theoretical tool used for its security proof is called the leftover hashing lemma (LHL). We present a direct connection between the LHL and the coding theorem of a certain quantum error correction code. Then we apply this result to proving the equivalence between the two approaches to proving the security of QKD.

arXiv:1809.05479•IEEE Transactions on Information Theory•Jan 27, 2020•19 citations

Everlasting security of quantum key distribution with 1K-DWCDM and quadratic hash

Khodakhast Bibak, Robert Ritchie, Behrouz Zolfaghari

Quantum key distribution (QKD) offers a very strong property called everlasting security, which says if authentication is unbroken during the execution of QKD, the generated key remains information-theoretically secure indefinitely. For this purpose, we propose the use of certain universal hashing based MACs for use in QKD, which are fast, very efficient with key material, and are shown to be highly secure. Universal hash functions are ubiquitous in computer science with many applications ranging from quantum key distribution and information security to data structures and parallel computing. In QKD, they are used at least for authentication, error correction, and privacy amplification. Using results from Cohen [Duke Math. J., 1954], we also construct some new families of $\varepsilon$-almost-$\Delta$-universal hash function families which have much better collision bounds than the well-known Polynomial Hash. Then we propose a general method for converting any such family to an $\varepsilon$-almost-strongly universal hash function family, which makes them useful in a wide range of applications, including authentication in QKD.

Quantum Information and Computation•Feb 10, 2021•6 citations

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•38 citations

Authentication of variable length messages in quantum key distribution

Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan

Abstract Authentication plays a critical role in the security of quantum key distribution (QKD) protocols. We propose using Polynomial Hash and its variants for authentication of variable length messages in QKD protocols. Since universal hashing is used not only for authentication in QKD but also in other steps in QKD like error correction and privacy amplification, and also in several other areas of quantum cryptography, Polynomial Hash and its variants as the most efficient universal hash function families can be used in these important steps and areas, as well. We introduce and analyze several efficient variants of Polynomial Hash and, using deep results from number theory, prove that each variant gives an ε-almost-Δ-universal family of hash functions. We also give a general method for transforming any such family to an ε-almost-strongly universal family of hash functions. The latter families can then, among other applications, be used in the Wegman–Carter MAC construction which has been shown to provide a universally composable authentication method in QKD protocols. As Polynomial Hash has found many applications, our constructions and results are potentially of interest in various areas.

EPJ Quantum Technology•Feb 16, 2022•10 citations

Probability distributions over CSS codes: two-universality, QKD hashing, collision bounds, security

Pete Rigas

We characterize novel probability distributions for CSS codes. Such classes of error correcting codes, originally introduced by Calderbank, Shor, and Steane, are of great significance in advancing the fidelity of Quantum computation, with implications for future near term applications. Within the context of Quantum key distribution, such codes, as examined by Ostrev in arXiv: 2109.06709 along with two-universal hashing protocols, have greatly simplified Quantum phases of computation for unconditional security. To further examine novel applications of two-universal hashing protocols, particularly through the structure of parity check matrices, we demonstrate how being able to efficiently compute functions of the parity check matrices relates to marginals of a suitably defined probability measure supported over random matrices. The security of the two-universal QKD hashing protocol will be shown to depend upon the computation of purified states of random matrices, which relates to probabilistic collision bounds between two hashing functions. Central to our approach are the introduction of novel real, simulator, and ideal, isometries, hence allowing for efficient computations of functions of the two parity check matrices. As a result of being able to perform such computations involving parity check matrices, the security of the two-universal hashing protocol is a factor of $2^{ \frac{5}{2} ( 5 - \frac{3}{2} ) + \mathrm{log}_2 \sqrt{C}}$ less secure, for some strictly positive constant $C$.

arXiv:2510.02402•Oct 1, 2025•0 citations

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.

Calderbank-Shor-Steane (CSS) quantum error-correcting codes are based on pairs of classical codes which are mutually dual containing. Explicit constructions of such codes for large blocklengths and with good error correcting properties are not easy to find. In this paper we propose a construction of CSS codes which combines a classical code with a two-universal hash function. We show, using the results of Renner and Koenig, that the communication rates of such codes approach the hashing bound on tensor powers of Pauli channels in the limit of large block-length. While the bit-flip errors can be decoded as efficiently as the classical code used, the problem of efficiently decoding the phase-flip errors remains open.

We show that the Mayers-Shor-Preskill approach and Renner's approach to proving the security of quantum key distribution (QKD) are essentially the same. We begin our analysis by considering a special case of QKD called privacy amplification (PA). PA itself is an important building block of cryptography, both classical and quantum. The standard theoretical tool used for its security proof is called the leftover hashing lemma (LHL). We present a direct connection between the LHL and the coding theorem of a certain quantum error correction code. Then we apply this result to proving the equivalence between the two approaches to proving the security of QKD.

Quantum key distribution (QKD) offers a very strong property called everlasting security, which says if authentication is unbroken during the execution of QKD, the generated key remains information-theoretically secure indefinitely. For this purpose, we propose the use of certain universal hashing based MACs for use in QKD, which are fast, very efficient with key material, and are shown to be highly secure. Universal hash functions are ubiquitous in computer science with many applications ranging from quantum key distribution and information security to data structures and parallel computing. In QKD, they are used at least for authentication, error correction, and privacy amplification. Using results from Cohen [Duke Math. J., 1954], we also construct some new families of

\varepsilon

-almost-

\Delta

-universal hash function families which have much better collision bounds than the well-known Polynomial Hash. Then we propose a general method for converting any such family to an

\varepsilon

-almost-strongly universal hash function family, which makes them useful in a wide range of applications, including authentication in QKD.

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.

Abstract Authentication plays a critical role in the security of quantum key distribution (QKD) protocols. We propose using Polynomial Hash and its variants for authentication of variable length messages in QKD protocols. Since universal hashing is used not only for authentication in QKD but also in other steps in QKD like error correction and privacy amplification, and also in several other areas of quantum cryptography, Polynomial Hash and its variants as the most efficient universal hash function families can be used in these important steps and areas, as well. We introduce and analyze several efficient variants of Polynomial Hash and, using deep results from number theory, prove that each variant gives an ε-almost-Δ-universal family of hash functions. We also give a general method for transforming any such family to an ε-almost-strongly universal family of hash functions. The latter families can then, among other applications, be used in the Wegman–Carter MAC construction which has been shown to provide a universally composable authentication method in QKD protocols. As Polynomial Hash has found many applications, our constructions and results are potentially of interest in various areas.

We characterize novel probability distributions for CSS codes. Such classes of error correcting codes, originally introduced by Calderbank, Shor, and Steane, are of great significance in advancing the fidelity of Quantum computation, with implications for future near term applications. Within the context of Quantum key distribution, such codes, as examined by Ostrev in arXiv: 2109.06709 along with two-universal hashing protocols, have greatly simplified Quantum phases of computation for unconditional security. To further examine novel applications of two-universal hashing protocols, particularly through the structure of parity check matrices, we demonstrate how being able to efficiently compute functions of the parity check matrices relates to marginals of a suitably defined probability measure supported over random matrices. The security of the two-universal QKD hashing protocol will be shown to depend upon the computation of purified states of random matrices, which relates to probabilistic collision bounds between two hashing functions. Central to our approach are the introduction of novel real, simulator, and ideal, isometries, hence allowing for efficient computations of functions of the two parity check matrices. As a result of being able to perform such computations involving parity check matrices, the security of the two-universal hashing protocol is a factor of

2^{ \frac{5}{2} ( 5 - \frac{3}{2} ) + \mathrm{log}_2 \sqrt{C}}

less secure, for some strictly positive constant

C

.