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

Quantum Information and Computation

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

Khodakhast Bibak, Robert Ritchie, Behrouz Zolfaghari

Published Feb 10, 2021• 6 citations
Publisher

Abstract

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.

DOI
10.26421/qic21.3-4-1

Related papers

Authentication in Quantum Key Distribution : Security Proof and Universal Hash Functions

Aysajan Abidin

Quantum Key Distribution (QKD) is a secret key agreement technique that consists of two parts: quantum transmission and measurement on a quantum channel, and classical post-processing on a public communication channel. It enjoys provable unconditional security provided that the public communication channel is immutable. Otherwise, QKD is vulnerable to a man-in-the-middle attack. Immutable public communication channels, however, do not exist in practice. So we need to use authentication that implements the properties of an immutable channel as well as possible. One scheme that serves this purpose well is the Wegman-Carter authentication (WCA), which is built upon Almost Strongly Universal2 (ASU2) hashing. This scheme uses a new key in each authentication attempt to select a hash function from an ASU2 family, which is then used to generate the authentication tag for a message. The main focus of this dissertation is on authentication in the context of QKD. We study ASU2 hash functions, security of QKD that employs a computationally secure authentication, and also security of authentication with a partially known key. Specifically, we study the following. First, Universal hash functions and their constructions are reviewed, and as well as a new construction of ASU2 hash functions is presented. Second, security of QKD that employs a specific computationally secure authentication is studied. We present detailed attacks on various practical implementations of QKD that employs this authentication. We also provide countermeasures and prove necessary and sufficient conditions for upgrading the security of the authentication to the level of unconditional security. Third, Universal hash function based multiple authentication is studied. This uses a fixed ASU2 hash function followed by one-time pad encryption, to keep the hash function secret. We show that the one-time pad is necessary in every round for the authentication to be unconditionally secure. Lastly, we study security of the WCA scheme, in the case of a partially known authentication key. Here we prove tight information-theoretic security bounds and also analyse security using witness indistinguishability as used in the Universal Composability framework.

•Jan 1, 2013•15 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•14 citations

Quantum cryptography and authentication with low key-consumption

Aysajan Abidin, Christoph Pacher, Thomas Lorünser +2 more

Quantum Key Distribution (QKD - also referred to as Quantum Cryptography) is a technique for secret key agreement. It has been shown that QKD rigged with Information-Theoretic Secure (ITS) authentication (using secret key) of the classical messages transmitted during the key distribution protocol is also ITS. Note, QKD without any authentication can trivially be broken by man-in-the-middle attacks. Here, we study an authentication method that was originally proposed because of its low key consumption; a two-step authentication that uses a publicly known hash function, followed by a secret strongly universal2 hash function, which is exchanged each round. This two-step authentication is not information-theoretically secure but it was argued that nevertheless it does not compromise the security of QKD. In the current contribution we study intrinsic weaknesses of this approach under the common assumption that the QKD adversary has access to unlimited resources including quantum memories. We consider one implementation of Quantum Cryptographic protocols that use such authentication and demonstrate an attack that fully extract the secret key. Even including the final key from the protocol in the authentication does not rule out the possibility of these attacks. To rectify the situation, we propose a countermeasure that, while not information-theoretically secure, restores the need for very large computing power for the attack to work. Finally, we specify conditions that must be satisfied by the two-step authentication in order to restore information-theoretic security.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Oct 6, 2011•4 citations

Unconditionally secure authentication for quantum key distribution

Simon Calimani

This work describes the using of Universal and Strongly Universal classes of hash functions for unconditionally secure message authentication in quantum cryptogra- phy. Different classes are compared and constructions of flexible e-Almost Strongly Universal classes are described. A new upper bound on the lifetime of a single hash function in one-time padded tags is introduced and optimisation on the final QKD key rate is shown for the QuAKE experiment, a B92 based QKD system. The public channel communication protocol of QuAKE is described, with special stress on the security issues

•Dec 13, 2011•2 citations

Robust Message Authentication in the context of Quantum Key Distribution

Jothi Rangasamy, Dillibabu Shanmugam

Universal hashing-based message authentication code (MAC) is used as the de facto method to achieve information-theoretically secure authentication in quantum key distribution. We present a critical look at the most widely used type, namely Wegman-Carter MAC based on polynomial hashing and analyse its robustness against physical attacks exploiting side information. In particular, we mount a classical DPA attack on the hash part of the Wegman-Carter MAC which leads to a possible intercept-and-resend attack on the BB84-like QKD protocols. We illustrate this case with polynomial-evaluation MACs as their variants are used in commercial QKD systems. We show that our attack methodology is much simpler compared to that of Belaid et al. at ASIACRYPT 2014. Finally, we present an algebraic countermeasure so that the resulting MAC is not susceptible to the identified attack.

International Journal of Information and Computer Security•Jan 1, 2022•1 citation

Using Hash-Based Signatures to Bootstrap Quantum Key Distribution

Sébastien Kunz-Jacques, Paul Jouguet

Quantum Key Distribution is a secret distribution technique that requires an authenticated channel. This channel is usually created on top of an un-authenticated communication medium using unconditionally secure Message Authentication Codes (MAC) and an initial common secret. We examine the consequences of replacing this MAC algorithm by a cryptographic hash-based signature algorithm, like the Lamport algorithm. We show that provided one-way functions exist, the Lamport algorithm or its variants can be instantiated in a secure way in the Universally Composable sense, and can therefore be plugged into any QKD protocol with a composable security proof in a secure manner. This association, while relying on short-term computational hardness assumptions, results in an increase of the practical security of QKD and eases its deployment.

arXiv:1109.2844•Sep 13, 2011•6 citations
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 Key Distribution (QKD) is a secret key agreement technique that consists of two parts: quantum transmission and measurement on a quantum channel, and classical post-processing on a public communication channel. It enjoys provable unconditional security provided that the public communication channel is immutable. Otherwise, QKD is vulnerable to a man-in-the-middle attack. Immutable public communication channels, however, do not exist in practice. So we need to use authentication that implements the properties of an immutable channel as well as possible. One scheme that serves this purpose well is the Wegman-Carter authentication (WCA), which is built upon Almost Strongly Universal2 (ASU2) hashing. This scheme uses a new key in each authentication attempt to select a hash function from an ASU2 family, which is then used to generate the authentication tag for a message. The main focus of this dissertation is on authentication in the context of QKD. We study ASU2 hash functions, security of QKD that employs a computationally secure authentication, and also security of authentication with a partially known key. Specifically, we study the following. First, Universal hash functions and their constructions are reviewed, and as well as a new construction of ASU2 hash functions is presented. Second, security of QKD that employs a specific computationally secure authentication is studied. We present detailed attacks on various practical implementations of QKD that employs this authentication. We also provide countermeasures and prove necessary and sufficient conditions for upgrading the security of the authentication to the level of unconditional security. Third, Universal hash function based multiple authentication is studied. This uses a fixed ASU2 hash function followed by one-time pad encryption, to keep the hash function secret. We show that the one-time pad is necessary in every round for the authentication to be unconditionally secure. Lastly, we study security of the WCA scheme, in the case of a partially known authentication key. Here we prove tight information-theoretic security bounds and also analyse security using witness indistinguishability as used in the Universal Composability framework.
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.
Quantum Key Distribution (QKD - also referred to as Quantum Cryptography) is a technique for secret key agreement. It has been shown that QKD rigged with Information-Theoretic Secure (ITS) authentication (using secret key) of the classical messages transmitted during the key distribution protocol is also ITS. Note, QKD without any authentication can trivially be broken by man-in-the-middle attacks. Here, we study an authentication method that was originally proposed because of its low key consumption; a two-step authentication that uses a publicly known hash function, followed by a secret strongly universal2 hash function, which is exchanged each round. This two-step authentication is not information-theoretically secure but it was argued that nevertheless it does not compromise the security of QKD. In the current contribution we study intrinsic weaknesses of this approach under the common assumption that the QKD adversary has access to unlimited resources including quantum memories. We consider one implementation of Quantum Cryptographic protocols that use such authentication and demonstrate an attack that fully extract the secret key. Even including the final key from the protocol in the authentication does not rule out the possibility of these attacks. To rectify the situation, we propose a countermeasure that, while not information-theoretically secure, restores the need for very large computing power for the attack to work. Finally, we specify conditions that must be satisfied by the two-step authentication in order to restore information-theoretic security.
This work describes the using of Universal and Strongly Universal classes of hash functions for unconditionally secure message authentication in quantum cryptogra- phy. Different classes are compared and constructions of flexible e-Almost Strongly Universal classes are described. A new upper bound on the lifetime of a single hash function in one-time padded tags is introduced and optimisation on the final QKD key rate is shown for the QuAKE experiment, a B92 based QKD system. The public channel communication protocol of QuAKE is described, with special stress on the security issues
Universal hashing-based message authentication code (MAC) is used as the de facto method to achieve information-theoretically secure authentication in quantum key distribution. We present a critical look at the most widely used type, namely Wegman-Carter MAC based on polynomial hashing and analyse its robustness against physical attacks exploiting side information. In particular, we mount a classical DPA attack on the hash part of the Wegman-Carter MAC which leads to a possible intercept-and-resend attack on the BB84-like QKD protocols. We illustrate this case with polynomial-evaluation MACs as their variants are used in commercial QKD systems. We show that our attack methodology is much simpler compared to that of Belaid et al. at ASIACRYPT 2014. Finally, we present an algebraic countermeasure so that the resulting MAC is not susceptible to the identified attack.
Quantum Key Distribution is a secret distribution technique that requires an authenticated channel. This channel is usually created on top of an un-authenticated communication medium using unconditionally secure Message Authentication Codes (MAC) and an initial common secret. We examine the consequences of replacing this MAC algorithm by a cryptographic hash-based signature algorithm, like the Lamport algorithm. We show that provided one-way functions exist, the Lamport algorithm or its variants can be instantiated in a secure way in the Universally Composable sense, and can therefore be plugged into any QKD protocol with a composable security proof in a secure manner. This association, while relying on short-term computational hardness assumptions, results in an increase of the practical security of QKD and eases its deployment.