Paper 2009/153 Original: eprint.iacr.org/2009/153 ↗
A new bound for t−wise almost universal hash functions
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2011-12-11: last updated
- 2009-04-07: published
- Short URL
- https://ia.cr/2009/153
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}