Dual Universality of Hash Functions and Its Applications to Quantum Cryptography

• Published in: IEEE transactions on information theory 2013-07, Vol.59 (7), p.4700-4717
• Main Authors: Tsurumaru, T., Hayashi, M.
• Format: Article
• Language: English
• Subjects: Applied sciences; Calderbank-Shor-Steane (CSS) codes; Classical and quantum physics: mechanics and fields; Coding theory; Coding, codes; Cryptography; delta -biased family; dual function; Error correction & detection; Error correction codes; Exact sciences and technology; Information theory; Information, signal and communications theory; Kernel; Linear codes; Physics; Privacy; Quantum cryptography; Quantum information; quantum key distribution (QKD); Quantum physics; Signal and communications theory; Telecommunications and information theory; varepsilon -almost {\rm universal}_{2} hash functions; Vectors; {\rm universal}_{2} hash functions
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2013.2250576

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 family F and a code family C , and thereby defining ε-almost dual universal 2 hash functions, as a generalization of the conventional universal 2 hash 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.