New bound for almost universal hash funcions

Long H. Nguyen and Andrew W. Roscoe

Abstract

Using the pigeon-hole principle, we introduce a new lower bound for the key length in an almost universal hash function, which is tighter than another similar bound derived from a well-studied equivalence between almost universal hashes and error-correcting codes. The new bound turns out to be tighter than another similar bound derived from the equivalence between almost universal functions and error-correcting codes (i.e. the Singleton bound). To the best of my knowledge, this is the first time the equivalence is shown not to produce a tight bound for an almost universal hash functions. This result, perhaps paradoxically, does not imply that we can further improve the Singleton bound in coding theory, and I will explain why there is a mismatch in this talk.