Paper 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.
Note: Improvement on the main result (lower bound on key length of an almost universal hash functions) reported in this paper.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. We intend to submit this paper to a conference in the near future
- Keywords
- Bound of universal hash functions
- Contact author(s)
- Long Nguyen @ cs ox ac uk
- History
- 2011-12-11: last of 3 revisions
- 2009-04-07: received
- See all versions
- Short URL
- https://ia.cr/2009/153
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2009/153,
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},
url = {https://eprint.iacr.org/2009/153}
}
