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 m3 field elements is m/2 field multiplications. Typically, a field multiplication consists of a basic multiplication followed by a reduction. The new algorithm requires m/2 basic multiplications and 1+m/4 reductions. Based on the new algorithm for evaluating BRW polynomials, we propose two new hash functions BRW128 and BRW256 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 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},
      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.