Welcome to the resource topic for
**2014/890**

**Title:**

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

**Authors:**
Jean-Sebastien Coron, Arnab Roy, 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.

**ePrint:**
https://eprint.iacr.org/2014/890

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 .