CryptoDB

Paper: Trade-Off Between Key Size and Efficiency in Universal Hashing Using Polynomials

Authors: Palash Sarkar URL: http://eprint.iacr.org/2009/048 Search ePrint Search Google Consider the following universal hashing set-up. Let $\rF$ be a finite field and suppose any message consists of at most $2^{30}$ elements of $\rF$. Suppose further that a collision bound of $2^{-128}$ is desired. This can be achieved using usual polynomial hashing with $|\rF|\approx 2^{160}$ and having a digest of $160$ bits and a key of length also $160$ bits; hashing an $n$-bit message requires approximately $n/160$ multiplications over $\rF$. We describe a new hashing method which can achieve the same collision bound of $2^{-128}$ for messages of at most $L$ elements by working over a field $\rF$ of size $\approx 2^{136}$. Hashing an $n$-bit message requires approximately $n/136$ multiplications over $\rF$. Supposing similar efficiency in implementation of field arithmetic in both cases, the ratio of the two processing times is $160/136\times[M_{136}]/[M_{160}]$, where $M_a$ is the time for one multiplication in a field of size $\approx 2^a$. Since $M_a$ is quadratic in $a$, the new algorithm is expected to be faster than usual polynomial hashing. Further, the size of the digest also reduces to $136$ bits. The trade-off is that the key size increases to $5\times 136=680$ bits compared to the key size of $160$ bits for usual polynomial hashing. The method mentioned above is a special case of a general method of combining independent universal hash functions at multiple levels to obtain a new universal hash function. Other consequences of the new algorithm are worked out including how it can be instantiated by a class of polynomials introduced by Bernstein.
BibTeX
@misc{eprint-2009-18235,
title={Trade-Off Between Key Size and Efficiency in Universal Hashing Using Polynomials},
booktitle={IACR Eprint archive},
keywords={secret-key cryptography / universal hash function},
url={http://eprint.iacr.org/2009/048},
note={ palash@isical.ac.in 14272 received 28 Jan 2009},
author={Palash Sarkar},
year=2009
}