New combinatorial bounds for universal families of hash functions

Long H. Nguyen and Andrew W. Roscoe

abstract

We introduce a new lower bound on the key length, termed the "combinatorial" bound, in an ε-almost universal family of hash functions. This result gives us a lower bound on the bit-length of the hash key r with respect to the message bit-length K, the hash output bit-length b, and the hash collision probability ε. We derive the bound using combinatorial analysis, and also show how it corresponds to bounds for subsets of parameter values derived from the theory of error-correcting codes, and finite field arithmetic. We compare the bound against other well-known bounds of this and other universal families of hash functions. We discover that the value ε = [ 1 + b/(K-b) ] 2^-b represents an important "threshold" in the behaviour of bounds, quantifying the "Wegman-Carter" effect. We then move on to analyse how tightly our new bound is satisfied by many known ways of computing universal families of hash functions, including error-correcting codes, polynomial hashing over finite fields, and square hash with small key size. In addition to the combinatorial bound, a new lower bound on the key length of an almost XOR universal family of hash function is introduced.

info

links

BibTeX

Download (pdf)

related pages