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.
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.
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 construct the first Message Authentication Codes (MACs) that are existentially unforgeable against a quantum chosen message attack. These chosen message attacks model a quantum adversary’s ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a quantum secure PRF is sufficient for constructing a quantum secure MAC, a fact that is considerably harder to prove than its classical analogue. Next, we show that a variant of Carter-Wegman MACs can be proven to be quantum secure. Unlike the classical settings, we present an attack showing that a pair-wise independent hash family is insufficient to construct a quantum secure one-time MAC, but we prove that a four-wise independent family is sufficient for one-time security. Keywords: Quantum computing, MAC,chosen message attacks, post-quantum security 1
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.
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 ε-almost-Δ-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 ε-almost-strongly universal hash function family, which makes them useful in a wide range of applications, including authentication in QKD.
We give a new class of security definitions for authentication in the quantum setting. These definitions capture and strengthen existing definitions of security against quantum adversaries for both classical message authentication codes (MACs) and well as full quantum state authentication schemes. The main feature of our definitions is that they precisely characterize the effective behavior of any adversary when the authentication protocol accepts, including correlations with the key. Our definitions readily yield a host of desirable properties and interesting consequences; for example, our security definition for full quantum state authentication implies that the entire secret key can be re-used if the authentication protocol succeeds. Next, we present several protocols satisfying our security definitions. We show that the classical Wegman-Carter authentication scheme with 3-universal hashing is secure against superposition attacks, as well as adversaries with quantum side information. We then present conceptually simple constructions of full quantum state authentication. Finally, we prove a lifting theorem which shows that, as long as a protocol can securely authenticate the maximally entangled state, it can securely authenticate any state, even those that are entangled with the adversary. Thus, this shows that protocols satisfying a fairly weak form of authentication security automatically satisfy a stronger notion of security (in particular, the definition of Dupuis, et al (2012)).
We propose a quantum protocol to authenticate classical messages that can be used to replace Wegman–Carter’s classical authentication scheme in quantum key distribution (QKD) protocols. We show that the proposed scheme achieves greater conditional entropy of the seed for the intruder given her (quantum) observation than the classical case. The proposed scheme is suitable for situations where the shared symmetric key used in authentication becomes dangerously short (due to noise or eavesdropping), and there is a threat that it might be completely consumed without being replaced. Our protocol is an improvement over a classical scheme by Brassard and takes advantage of quantum channel properties. It is motivated by information-theoretical results. We stress that the proposed authentication protocol can also be used as an independent authentication protocol that is not a part of a QKD. However by adopting it, QKD becomes a fully quantum protocol. We prove that quantum resources can improve both the secrecy of the key generated by the PRG and the secrecy of the tag obtained with a hidden hash function. We conclude that the proposed quantum encoding offers more security than the classical scheme and, by applying a classical result, we show that it can be used under noisy quantum channels.