**A Fast Single-Key Two-Level Universal Hash Function**

*Debrup Chakraborty and Sebati Ghosh and Palash Sarkar*

**Abstract: **Universal hash functions based on univariate polynomials are well known, e.g. \sym{Poly1305} and \sym{GHASH}. Using
Horner's rule to evaluate such hash functions require $\ell-1$ field multiplications for hashing a message consisting of $\ell$
blocks where each block is one field element. A faster method is based on the class of Bernstein-Rabin-Winograd (BRW) polynomials
which require $\lfloor\ell/2\rfloor$ multiplications and $\lfloor\lg\ell\rfloor$ squarings for $\ell\geq 3$ blocks.
Though this is significantly smaller than Horner's rule based hashing, implementation of BRW polynomials for variable length
messages present significant difficulties. In this work, we propose a two-level hash function where BRW polynomial based
hashing is done at the lower level and Horner's rule based hashing is done at the higher level. The BRW polynomial based
hashing is applied to a fixed number of blocks and hence the difficulties in handling variable length messages is avoided.
Even though the hash function has two levels, we show that it is sufficient to use a single field element as the hash key. The
basic idea is instantiated to propose two new hash functions, one which hashes a single binary string and the other can hash a vector
of binary strings. We describe two actual implementations, one over $\mathbb{F}_{2^{128}}$ and the other over
$\mathbb{F}_{2^{256}}$ both using the {\tt pclmulqdq} instruction available in modern Intel processors. On both the Haswell and
Skylake processors, the implementation over $\mathbb{F}_{2^{128}}$ is faster than the highly optimised implementation of \sym{GHASH}
by Gueron.
We further show that the Fast Fourier Transform based field multiplication over $\mathbb{F}_{2^{256}}$ proposed by Bernstein and Chou
can be used to evaluate the new hash function at a cost of about at most 46 bit operations per bit of digest, but, unlike the
Bernstein-Chou analysis, there is no hidden cost of generating the hash key.
More generally, the new idea of building a two-level hash function having a single field element as the hash key can be applied to other
finite fields to build new hash functions.

**Category / Keywords: **universal hash function, Horner's rule, BRW polynomials, two-level hash function, MAC schemes.

**Date: **received 23 Nov 2016

**Contact author: **debrup at isical ac in, sebati1987@gmail com, palash@isical ac in

**Available format(s): **PDF | BibTeX Citation

**Version: **20161123:191731 (All versions of this report)

**Short URL: **ia.cr/2016/1103

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]