Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / universal hash function, BRW polynomials

Date: received 13 Apr 2017, last revised 2 Nov 2017

Contact author: palash at isical ac in

Available format(s): PDF | BibTeX Citation

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.

Version: 20171102:104333 (All versions of this report)

Short URL: ia.cr/2017/328

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]