Universal hashing and authentication codes

In this paper, we study the application of universal hashing to the construction of unconditionally secure authentication codes without secrecy. This idea is most useful when the number of authenticators is exponentially small compared to the number of possible source states (plaintext messages). We formally define some new classes of hash functions and then prove some new bounds and give some general constructions for these classes of hash functions. Then we discuss the implications to authentication codes.A preliminary version of this paper was presented at CRYPTO '91 and appeared in Lecture Notes in Computer Science, vol. 576, pp. 74–85, Springer-Verlag, 1992.