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

Category / Keywords: secret-key cryptography / Universal Hash, AXU hash, multivariate polynomial, error correcting code, Vandermonde matrix, Toeplitz hash.