Welcome to the resource topic for 2013/574
Title:
On the Minimum Number of Multiplications Necessary for Universal Hash Constructions
Authors: 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.
ePrint: https://eprint.iacr.org/2013/574
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .