You are looking at a specific version 20090730:111907 of this paper. See the latest version.

Paper 2009/048

A Trade-Off Between Collision Probability and Key Size in Universal Hashing Using Polynomials

Palash Sarkar

Abstract

Let $\rF$ be a finite field and suppose that a single element of $\rF$ is used as an authenticator (or tag). Further, suppose that any message consists of at most $L$ elements of $\rF$. For this setting, usual polynomial based universal hashing achieves a collision bound of $(L-1)/|\rF|$ using a single element of $\rF$ as the key. The well-known multi-linear hashing achieves a collision bound of $1/|\rF|$ using $L$ elements of $\rF$ as the key. In this work, we present a new universal hash function which achieves a collision bound of $m\lceil\log_m L\rceil/|\rF|$, $m\geq 2$, using $1+\lceil\log_m L\rceil$ elements of $\rF$ as the key. This provides a new trade-off between key size and collision probability for universal hash functions.

Note: A substantial revision. The current version discusses the trade-off between key size and collision probability assuming a fixed size authenticator. This trade-off is clearer than the previous version which had discussed the trade-off between key size and efficiency for a fixed collision probability. Also, the current version discusses the relation of the construction to previous work by Stinson.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
universal hash function
Contact author(s)
palash @ isical ac in
History
2009-07-30: revised
2009-01-29: received
See all versions
Short URL
https://ia.cr/2009/048
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.