On the Minimum Number of Multiplications Necessary for Universal Hash Functions

Abstract. Let d ≥ 1 be an integer and R1 be a finite ring whose el-ements are called block. A d-block universal hash over R1 is a vector of d multivariate polynomials in message and key block such that the maximum differential probability of the hash function is “low”. Two such single block hashes are pseudo dot-product (PDP) hash and Bernstein-Rabin-Winograd (BRW) hash which require n 2 multiplications for n mes-sage blocks. The Toeplitz construction and d independent invocations of PDP are d-block hash outputs which require d × n 2 multiplications. How-ever, here we show that at least (d − 1) + n 2 multiplications are necessary to compute a universal hash over n message blocks. We construct a d-block universal hash, called EHC, which requires the matching (d−1)+ n 2 multiplications for d ≤ 4. Hence it is optimum and our lower bound is tight when d ≤ 4. It has similar parllelizibility, key size like Toeplitz and so it can be used as a light-weight universal hash