A trade-off between collision probability and key size in universal hashing using polynomials

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