Polynomial Hashing over Prime Order Fields

Sreyosi Bhattacharyya; Kaushik Nath; Palash Sarkar

Paper 2023/634

Polynomial Hashing over Prime Order Fields

Sreyosi Bhattacharyya, Indian Statistical Institute

Kaushik Nath, Indian Statistical Institute

Palash Sarkar, Indian Statistical Institute

Abstract

This paper makes a comprehensive study of two important strategies for polynomial hashing over a prime order field $F_{p}$ , namely usual polynomial based hashing and hashing based on Bernstein-Rabin-Winograd (BRW) polynomials, and the various ways to combine them. Several hash functions are proposed and upper bounds on their differential probabilities are derived. Concrete instantiations are provided for the primes $p = 2^{127} - 1$ and $p = 2^{130} - 5$ . A major contribution of the paper is an extensive 64-bit implementation of all the proposed hash functions in assembly targeted at modern Intel processors. The timing results suggest that using the prime is significantly faster than using the prime . Further, a judicious mix of the usual polynomial based hashing and BRW-polynomial based hashing can provide a significantly faster alternative to only usual polynomial based hashing. In particular, the timing results of our implementations show that our final hash function proposal for the prime is much faster than the well known Poly1305 hash function defined over the prime , achieving speed improvements of up to 40%.

Note: Corrected typos and improved the presentation.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: almost XOR universal hash function polynomial hash BRW hash
Contact author(s): bhattacharyya sreyosi @ gmail com
kaushik nath @ yahoo in
palash @ isical ac in
History: 2023-10-29: revised; 2023-05-04: received; See all versions
Short URL: https://ia.cr/2023/634
License: CC BY

BibTeX

@misc{cryptoeprint:2023/634,
      author = {Sreyosi Bhattacharyya and Kaushik Nath and Palash Sarkar},
      title = {Polynomial Hashing over Prime Order Fields},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/634},
      year = {2023},
      url = {https://eprint.iacr.org/2023/634}
}