Dual Universality of Hash Functions and Its Applications to Quantum Cryptography
Toyohiro Tsurumaru, M. Hayashi
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 familyFand a code familyC, and thereby defining ε-almost dual universal2hash functions, as a generalization of the conventional universal2hash 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.
arXiv:1101.0064•IEEE Transactions on Information Theory•Apr 2, 2013•55 citations