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.
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) 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.