Paper 2009/153

A new bound for t−wise almost universal hash functions

Long Hoang Nguyen and A. W. Roscoe


Using the pigeon-hole principle, we derive a new bound for the key length in a t-wise almost universal hash function where the multicollision or t-collision probability is bounded above by epsilon in the range [0,1]. The important features of this bound are (1) it decreases very slowly as t increases, and (2) the key length grows at least linearly with the logarithm of the message length. To our knowledge, this is the first almost universal hash bound for any integer t > 1. This work arises from the use of t-wise almost universal hash functions in manual authentication protocols.

Note: Improvement on the main result (lower bound on key length of an almost universal hash functions) reported in this paper.

Available format(s)
Publication info
Published elsewhere. We intend to submit this paper to a conference in the near future
Bound of universal hash functions
Contact author(s)
Long Nguyen @ cs ox ac uk
2011-12-11: last of 3 revisions
2009-04-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Long Hoang Nguyen and A.  W.  Roscoe},
      title = {A new bound for t−wise almost universal hash functions},
      howpublished = {Cryptology ePrint Archive, Paper 2009/153},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.