Combinatorial techniques for universal hashing

摘要

The idea of a universal class of hash functions is due to Carter and Wegman. The goal is to define a collection of hash functions in such a way that a random choice of a function in the class yields a low probability that any two distinct inputs will collide. In this paper, we present some characterizations of universal classes of hash functions in terms of combinatorial designs such as resolvable balanced incomplete block designs and orthogonal arrays. The two classes of hash functions that we study are called optimally universal and strongly universal. We show that optimally universal classes of hash functions are equivalent to resolvable balanced incomplete block designs and strongly universal classes are equivalent to orthogonal arrays. Consequently, known classes of combinatorial designs yield new, small, and efficient classes of universal hash functions.