**Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-channel Countermeasures**

*Jean-Sebastien Coron and Arnab Roy and Srinivas Vivek*

**Abstract: **We describe a new technique for evaluating polynomials over binary finite fields. This is useful in the context of anti-DPA countermeasures when an S-box is expressed as a polynomial over a binary finite field. For $n$-bit S-boxes our new technique has heuristic complexity ${\cal O}(2^{n/2}/\sqrt{n})$ instead of ${\cal O}(2^{n/2})$ proven complexity for the Parity-Split method. We also prove a lower bound of ${\Omega}(2^{n/2}/\sqrt{n})$ on the complexity of any method to evaluate $n$-bit S-boxes; this shows that our method is asymptotically optimal. Here, complexity refers to the number of non-linear multiplications required to evaluate the polynomial corresponding to an S-box.

In practice we can evaluate any $8$-bit S-box in $10$ non-linear multiplications instead of $16$ in the Roy-Vivek paper from CHES 2013, and the DES S-boxes in $4$ non-linear multiplications instead of $7$. We also evaluate any $4$-bit S-box in $2$ non-linear multiplications instead of $3$. Hence our method achieves optimal complexity for the PRESENT S-box.

**Category / Keywords: **implementation / side-channel countermeasure, masking, polynomial evaluation, finite field

**Original Publication**** (with major differences): **IACR-CHES-2014

**Date: **received 28 Oct 2014

**Contact author: **jean-sebastien coron at uni lu; srinivasvivek venkatesh@uni lu; arroy@dtu dk

**Available format(s): **PDF | BibTeX Citation

**Note: **This is the full version of the paper in the proceedings of CHES 2014.

**Version: **20141030:133810 (All versions of this report)

**Short URL: **ia.cr/2014/890

[ Cryptology ePrint archive ]