New bound for almost universal hash funcions
Long H. Nguyen and Andrew W. Roscoe abstract
Using the pigeon-hole principle, we introduce a new lower bound for the key length in an almost universal hash function, which is tighter than another similar bound derived from a well-studied equivalence between almost universal hashes and error-correcting codes. The new bound turns out to be tighter than another similar bound derived from the equivalence between almost universal functions and error-correcting codes (i.e. the Singleton bound). To the best of my knowledge, this is the first time the equivalence is shown not to produce a tight bound for an almost universal hash functions. This result, perhaps paradoxically, does not imply that we can further improve the Singleton bound in coding theory, and I will explain why there is a mismatch in this talk.
infojournal | Presented at the Summer School on Proable Security 2009 |
year | 2009 |
links
BibTeX
Download (pdf)
Link (pdf)
related pages
|
