Bucket Hashing and its Application to Fast Message Authentication

Author: Phillip Rogaway

Reference: Jounral of Cryptology, vol. 12, pp. 91-115, 1999. Prelminary version in Advances in Cryptology - CRYPTO '95, Lecture Notes in Computer Science, Vol. 963, D. Coppersmith, ed., Springer-Verlag, 1995.

Abstract: We introduce a new technique for constructing a family of universal hash functions. At its center is a simple metaphor: to hash a string x cast each of its words into a small number of buckets; xor the contents of each bucket; then collect up all the buckets' contents. Used in the context of Wegman-Carter authentication, this style of hash function provides a fast approach for software message authentication.

Full version available in PDF or PostScript.

Rogaway's home page.