Paper 2014/890
Fast Evaluation of Polynomials over Binary Finite Fields and Application to Sidechannel Countermeasures
JeanSebastien 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 antiDPA countermeasures when an Sbox is expressed as a polynomial over a binary finite field. For $n$bit Sboxes our new technique has heuristic complexity ${\cal O}(2^{n/2}/\sqrt{n})$ instead of ${\cal O}(2^{n/2})$ proven complexity for the ParitySplit method. We also prove a lower bound of ${\Omega}(2^{n/2}/\sqrt{n})$ on the complexity of any method to evaluate $n$bit Sboxes; this shows that our method is asymptotically optimal. Here, complexity refers to the number of nonlinear multiplications required to evaluate the polynomial corresponding to an Sbox. In practice we can evaluate any $8$bit Sbox in $10$ nonlinear multiplications instead of $16$ in the RoyVivek paper from CHES 2013, and the DES Sboxes in $4$ nonlinear multiplications instead of $7$. We also evaluate any $4$bit Sbox in $2$ nonlinear multiplications instead of $3$. Hence our method achieves optimal complexity for the PRESENT Sbox.
Note: This is the full version of the paper in the proceedings of CHES 2014.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 A major revision of an IACR publication in CHES 2014
 Keywords
 sidechannel countermeasuremaskingpolynomial evaluationfinite field
 Contact author(s)

jeansebastien coron @ uni lu
srinivasvivek venkatesh @ uni lu
arroy @ dtu dk  History
 20141030: received
 Short URL
 https://ia.cr/2014/890
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/890, author = {JeanSebastien Coron and Arnab Roy and Srinivas Vivek}, title = {Fast Evaluation of Polynomials over Binary Finite Fields and Application to Sidechannel Countermeasures}, howpublished = {Cryptology {ePrint} Archive, Paper 2014/890}, year = {2014}, url = {https://eprint.iacr.org/2014/890} }