Paper 2016/1103

A Fast Single-Key Two-Level Universal Hash Function

Debrup Chakraborty, 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.