Paper 2017/328

Evaluating Bernstein-Rabin-Winograd Polynomials

Sebati Ghosh and Palash Sarkar

Abstract

We describe an algorithm which can efficiently evaluate Bernstein-Rabin-Winograd (BRW) polynomials. The presently best known complexity of evaluating a BRW polynomial on $m\geq 3$ field elements is $\lfloor m/2\rfloor$ field multiplications. Typically, a field multiplication consists of a basic multiplication followed by a reduction. The new algorithm requires $\lfloor m/2\rfloor$ basic multiplications and $1+\lfloor m/4\rfloor$ reductions. Based on the new algorithm for evaluating BRW polynomials, we propose two new hash functions ${\sf BRW}128$ and ${\sf BRW}256$ with digest sizes $128$ bits and $256$ bits respectively. The practicability of these hash functions is demonstrated by implementing them using instructions available on modern Intel processors. Timing results obtained from the implementations suggest that ${\sf BRW}$ based hashing compares favourably to the highly optimised implementation by Gueron of Horner's rule based hash function.

Note: This is a significantly expanded version of the previous report. It includes the proof of correctness of the algorithm and the design of two concrete hash functions. Note: Debrup Chakraborty requested to be dropped from the author list.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
universal hash functionBRW polynomials
Contact author(s)
palash @ isical ac in
History
2017-11-02: last of 2 revisions
2017-04-17: received
See all versions
Short URL
https://ia.cr/2017/328
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/328,
      author = {Sebati Ghosh and Palash Sarkar},
      title = {Evaluating Bernstein-Rabin-Winograd Polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2017/328},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/328}},
      url = {https://eprint.iacr.org/2017/328}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.