**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.

**Category / Keywords: **secret-key cryptography / universal hash function

**Date: **received 28 Jan 2009, last revised 30 Jul 2009

**Contact author: **palash at isical ac in

**Available format(s): **PDF | BibTeX Citation

**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.

**Version: **20090730:111907 (All versions of this report)

**Short URL: **ia.cr/2009/048

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]