Paper 2014/890

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

Jean-Sebastien Coron, 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 $$-bit S-boxes our new technique has heuristic complexity $$ instead of $$ proven complexity for the Parity-Split method. We also prove a lower bound of $$ on the complexity of any method to evaluate $$-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 $$-bit S-box in $$ non-linear multiplications instead of $$ in the Roy-Vivek paper from CHES 2013, and the DES S-boxes in $$ non-linear multiplications instead of $$. We also evaluate any $$-bit S-box in $$ non-linear multiplications instead of $$. Hence our method achieves optimal complexity for the PRESENT S-box.

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