Welcome to the resource topic for 2017/328
Title:
Evaluating Bernstein-Rabin-Winograd Polynomials
Authors: Sebati Ghosh, 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.
ePrint: https://eprint.iacr.org/2017/328
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .