Fast universal hashing with small keys and no preprocessing: the PolyR construction

Authors: Ted Krovetz and Phillip Rogaway

Reference: Information Security and Cryptology - ICICS 2000, Lecture Notes in Computer Science, vol 2015, pp. 73-89, D.H. Won, ed., Springer-Verlag, 2000.

Abstract: We describe a universal hash-function family, PolyR, which hashes messages of effectively arbitrary length in 3.9-6.9 cycles/byte (cpb) on a Pentium II (achieving a collision probability in the range of 2^-16 to 2^-50). Unlike most proposals, PolyR actually hashes short messages faster (per byte) than long ones. At the same time, its key is only a few bytes, the output is only a few bytes, and no "preprocessing" is needed to achieve maximal efficiency. Our designs have been strongly influenced by low-level considerations relevant to software speed, and experimental results are given throughout.

Documentation:: pdf (176K)

Rogaway's home page.