Paper 2025/1262
Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields
, Indian Statistical Institute, KolkataAbstract
We introduce the new AXU hash function decBRWHash, which is parameterised by the positive integer $c$ and is based on Bernstein-Rabin-Winograd (BRW) polynomials. Choosing $c>1$ gives a hash function which can be implemented using $c$-way single instruction multiple data (SIMD) instructions. We report a set of very comprehensive hand optimised assembly implementations of 4-decBRWHash using avx2 SIMD instructions available on modern Intel processors. For comparison, we also report similar carefully optimised avx2 assembly implementations of polyHash, an AXU hash function based on usual polynomials. Our implementations are over prime order fields, specifically the primes $2^{127}-1$ and $2^{130}-5$. For the prime $2^{130}-5$, for avx2 implementations, compared to the famous Poly1305 hash function, 4-decBRWHash is faster for messages which are a few hundred bytes long and achieves a speed-up of about 16% for message lengths in a few kilobytes range and improves to a speed-up of about 23% for message lengths in a few megabytes range.
Note: Changes in Lemma 1, the discussion following Lemma 1 and the new remark numbered Remark 2.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- almost XOR universalBRW polynomialsSIMDassembly implementationavx2
- Contact author(s)
-
kaushik nath @ yahoo in
palash @ isical ac in - History
- 2025-10-01: revised
- 2025-07-08: received
- See all versions
- Short URL
- https://ia.cr/2025/1262
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1262,
author = {Kaushik Nath and Palash Sarkar},
title = {Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1262},
year = {2025},
url = {https://eprint.iacr.org/2025/1262}
}
