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 $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.

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

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
A major revision of an IACR publication in CHES 2014
Keywords
side-channel countermeasuremaskingpolynomial evaluationfinite field
Contact author(s)
jean-sebastien coron @ uni lu
srinivasvivek venkatesh @ uni lu
arroy @ dtu dk
History
2014-10-30: received
Short URL
https://ia.cr/2014/890
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/890,
      author = {Jean-Sebastien Coron and Arnab Roy and Srinivas Vivek},
      title = {Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-channel Countermeasures},
      howpublished = {Cryptology ePrint Archive, Paper 2014/890},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/890}},
      url = {https://eprint.iacr.org/2014/890}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.