You are looking at a specific version 20111211:105601 of this paper. See the latest version.

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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.