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.