Report

### 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 arise...

### Access Document

Files:
• (pdf, 288.3KB)

### Authors

Publisher:
OUCL
Publication date:
2010-11-01
UUID:
uuid:5528100b-95d9-47d3-bc7c-85067d885562
Local pid:
cs:3969
Deposit date:
2015-03-31