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

ISSN： 0925-1022

Source： Designs, Codes and Cryptography, Vol.58, Iss.3, 2011-03, pp. : 271-278

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

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