A new bound for t−wise almost universal hash functions
L.H. 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.
Details
| Institution |
OUCL |
| Month |
November |
| Number |
RR−10−24 |
| Pages |
4 |
| Year |
2010 |
Links
Related pages
|
People |