Bucket hashing and its application to fast message authentication (Q1291805)

A message authentication code (MAC) is often used to provide message authentication. Usually MAC generation and verification need to be done in software, i.e. frequent MAC computations over long strings call for fast techniques. Often, cryptographic hash functions are used to compute a MAC, however as shown by \textit{M. N. Wegman} and \textit{J. L. Carter} [J. Comput. Syst. Sci. 22, 265-279 (1981; Zbl 0461.68074)] it is not necessary to ``cryptographically'' transform the whole string (message). In this framework the problem of constructing a fast-to-compute MAC can be reduced to finding a family of almost universal hash functions whose members can be computed in a fast way. In the paper a new technique to construct a family of almost universal hash functions, called bucket hashing is introduced thus providing an extremely fast method to compute a MAC. After an introduction and survey of previous and subsequent work in the area, necessary definitions and basic properties of universal hash families are reviewed. Then bucket hashing is introduced and a particular bucket hashing scheme is analyzed and a detailed proof of the main theorem on upper bounds of the collision probability is given. In the second part of the paper the Wegman-Carter construction of a MAC from a given family of hash functions is reviewed, followed by an example of a concrete MAC based on the ideas of bucket hashing described in the previous sections. This example is also used to discuss some of the difficulties involved in constructing MAC using bucket hashing. Finally possible extensions of the approach are discussed and some open questions outlined.