Thumbnail
Access Restriction
Open

Author Nandi, Mridul
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Multiplication Necessary ♦ Minimum Number ♦ Universal Hash Function ♦ D-block Universal Hash ♦ Similar Parllelizibility ♦ Hash Function ♦ Multivariate Polynomial ♦ Message Block ♦ Light-weight Universal Hash ♦ Independent Invocation ♦ Toeplitz Construction ♦ Finite Ring ♦ Mes-sage Block ♦ Maximum Differential Probability ♦ Key Block ♦ Universal Hash ♦ D-block Hash Output ♦ Key Size ♦ Pseudo Dot-product ♦ Single Block Hash
Abstract 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.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article