**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.

**Date: **received 8 Sep 2013

**Contact author: **mridul nandi at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20130910:165508 (All versions of this report)

**Short URL: **ia.cr/2013/574

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]