Paper 2025/464

SoK: Efficient Design and Implementation of Polynomial Hash Functions over Prime Fields

Jean Paul Degabriele, Technology Innovation Institute
Jan Gilcher, ETH Zurich
Jérôme Govinden, TU Darmstadt
Kenneth G. Paterson, ETH Zurich
Abstract

Poly1305 is a widely-deployed polynomial hash function. The rationale behind its design was laid out in a series of papers by Bernstein, the last of which dates back to 2005. As computer architectures evolved, some of its design features became less relevant, but implementers found new ways of exploiting these features to boost its performance. However, would we still converge to this same design if we started afresh with today's computer architectures and applications? To answer this question, we gather and systematize a body of knowledge concerning polynomial hash design and implementation that is spread across research papers, cryptographic libraries, and developers' blogs. We develop a framework to automate the validation and benchmarking of the ideas that we collect. This approach leads us to five new candidate designs for polynomial hash functions. Using our framework, we generate and evaluate different implementations and optimization strategies for each candidate. We obtain substantial improvements over Poly1305 in terms of security and performance. Besides laying out the rationale behind our new designs, our paper serves as a reference for efficiently implementing polynomial hash functions, including Poly1305.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Major revision. 45th IEEE Symposium on Security and Privacy, IEEE S&P 2024
DOI
10.1109/SP54263.2024.00132
Keywords
SoKuniversal hashingpolynomial hash functionperformance
Contact author(s)
jeanpaul degabriele @ tii ae
jan gilcher @ inf ethz ch
jerome govinden @ tu-darmstadt de
kenny paterson @ inf ethz ch
History
2025-03-12: approved
2025-03-12: received
See all versions
Short URL
https://ia.cr/2025/464
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/464,
      author = {Jean Paul Degabriele and Jan Gilcher and Jérôme Govinden and Kenneth G. Paterson},
      title = {{SoK}: Efficient Design and Implementation of Polynomial Hash Functions over Prime Fields},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/464},
      year = {2025},
      doi = {10.1109/SP54263.2024.00132},
      url = {https://eprint.iacr.org/2025/464}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.