You are looking at a specific version 20140214:103637 of this paper. See the latest version.

Paper 2013/574

On the Minimum Number of Multiplications Necessary for Universal Hash Constructions

Mridul Nandi

Abstract

Let $d \geq 1$ be an integer and $R_1$ be a finite ring whose elements are called {\bf block}. A $d$-block universal hash over $R_1$ is a vector of $d$ multivariate polynomials in message and key block such that the maximum {\em differential probability} of the hash function is ``low''. Two such single block hashes are pseudo dot-product (\tx{PDP}) hash and Bernstein-Rabin-Winograd (\tx{BRW}) hash which require $\frac{n}{2}$ multiplications for $n$ message blocks. The Toeplitz construction and $d$ independent invocations of \tx{PDP} are $d$-block hash outputs which require $d \times \frac{n}{2}$ multiplications. However, here we show that {\em at least $(d-1) + \frac{n}{2}$ multiplications are necessary} to compute a universal hash over $n$ message blocks. We construct a {\em $d$-block universal hash, called \tx{EHC}, which requires the matching $(d -1) + \frac{n}{2}$ multiplications for $d \leq 4$}. Hence it is optimum and our lower bound is tight when $d \leq 4$. It has similar parllelizibility, key size like Toeplitz and so it can be used as a light-weight universal hash.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Universal HashAXU hashmultivariate polynomialerror correcting codeVandermonde matrixToeplitz hash.
Contact author(s)
mridul nandi @ gmail com
History
2014-02-14: revised
2013-09-10: received
See all versions
Short URL
https://ia.cr/2013/574
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.