Paper 2025/464
SoK: Efficient Design and Implementation of Polynomial Hash Functions over Prime Fields
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
-
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} }