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.