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