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.
The quantum key distribution (QKD) technology is achieving a growing interest in both the scientific and industrial communities. Based on principles of quantum mechanics, it can provide unconditional security in key exchanges over end-to-end communication channels. Information-theoretically secure (ITS) authentication, the compulsory procedure of QKD systems, avoids the man-in-the-middle attack during the security key generation. In this paper, we propose a novel family of almost strongly universal (ASU) hash functions based on number-theoretic transforms (N-ASU), and prove that N-ASU hash functions can meet the high security requirement of an ITS authentication procedure. With such N-ASU hash functions, we propose a novel efficient NTT-based authentication algorithm (N-Auth) for QKD systems. Such a solution offers nearly the same security guarantees provided by the available authentication algorithms built upon ASU hash functions, but is characterized by a much lower computational complexity. The experimental results show that the N-Auth algorithm can fully meet the real-time and high-performance demands of modern 10-GHz QKD systems, making it a viable solution for the implementation of industrial-strength unconditionally secure broadband communication solutions.