Cryptology ePrint Archive: Report 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.

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