Paper 2013/574

On the Minimum Number of Multiplications Necessary for Universal Hash Constructions

Mridul Nandi

Abstract

Let d1 be an integer and R1 be a finite ring whose elements are called {\bf block}. A d-block universal hash over R1 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 n2 multiplications for n message blocks. The Toeplitz construction and d independent invocations of \tx{PDP} are d-block hash outputs which require d×n2 multiplications. However, here we show that {\em at least (d1)+n2 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 (d1)+n2 multiplications for }. Hence it is optimum and our lower bound is tight when . 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

BibTeX

@misc{cryptoeprint:2013/574,
      author = {Mridul Nandi},
      title = {On the Minimum Number of Multiplications Necessary for Universal Hash Constructions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/574},
      year = {2013},
      url = {https://eprint.iacr.org/2013/574}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.