Hash families: Recursive constructions and applications to cryptography.

摘要

Hash families are basic combinatorial structures, which appear under various disguises in cryptology, database management, operating systems, and compiler construction. There are basically two types of hash families: perfect hash families and universal hash families. Applications of perfect hash families can be seen in broadcast encryption schemes, c-frameproof codes, visual cryptography, database management systems; and authentication code construction is an application of universal hash families.;An (N; n, m)-hash family is a finite set of N functions ;We give two recursive constructions for perfect hash families for any given values n, m, and w. We also give an algorithm to compute the hash function for any given values n, m, and w. Computation time of the hash function is ;We study the application of universal hashing to the construction of unconditionally secure authentication codes without secrecy. This idea is due to Wegman and Carter (67), who gave a construction which is useful when the number of authenticators is exponentially small compared to the number of possible source states (plaintext messages). Stinson generalized the Wegman and Carter construction by formally defining some new classes of hash functions (61). We generalize the Stinson construction and give applications to multiple authentications.