Paper 2013/574

On the Minimum Number of Multiplications Necessary for Universal Hash Constructions

Mridul Nandi

Abstract

Universal hashes are usually based on some multivariate polynomials in message and key blocks (elements of some underlying ring $R$). These are implemented by using multiplications (which dominates the computational time) and additions. Two such hashes are pseudo dot-product (\tx{PDP}) hash and Bernstein-Rabin-Winograd (\tx{BRW}) hash which require $n/2$ multiplications for $n$ message blocks. In this paper we observe that these are optimum in number of multiplications by showing that {\em at least $n/2$ multiplications or non-linear operations are necessary}. We also extend this lower bound for any multi-block hash construction, i.e., the hash output is an element of $R^d$. {\em We show that $d$ block hash outputs requires at least $(d -1) + n/2$ non-linear operations}. The widely used Toeplitz construction for $d$ block hash output requires $nd/2$ multiplications when it is applied for \tx{PDP}. In this paper, we propose a {\em $d$-block universal hash \tx{EHC} requiring $(d -1) + n/2$ multiplications and hence it is optimum and the bound is tight}. Our construction is roughly $d$ times faster than Toeplitz construction. Moreover, it has similar parllelizibility and key size as in Toeplitz construction.