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.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
universal hash functionHorner's ruleBRW polynomialstwo-level hash functionMAC schemes.
Contact author(s)
debrup @ isical ac in
sebati1987 @ gmail com
palash @ isical ac in
History
2016-11-23: received
Short URL
https://ia.cr/2016/1103
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1103,
      author = {Debrup Chakraborty and Sebati Ghosh and Palash Sarkar},
      title = {A Fast Single-Key Two-Level Universal Hash Function},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1103},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1103}},
      url = {https://eprint.iacr.org/2016/1103}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.