Cryptology ePrint Archive: Report 2009/153
A new bound for t−wise almost universal hash functions
Long Hoang Nguyen and A. W. Roscoe
Abstract: 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.
Category / Keywords: foundations / Bound of universal hash functions
Publication Info: We intend to submit this paper to a conference in the near future
Date: received 1 Apr 2009, last revised 11 Dec 2011
Contact author: Long Nguyen at cs ox ac uk
Available format(s): PDF | BibTeX Citation
Note: Improvement on the main result (lower bound on key length of an almost universal hash functions) reported in this paper.
Version: 20111211:105601 (All versions of this report)
Short URL: ia.cr/2009/153
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]