side-channel countermeasure; masking; polynomial evaluation; finite field
Abstract :
[en] 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.
Disciplines :
Computer science
Author, co-author :
Coron, Jean-Sébastien ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Roy, Arnab; University of Luxembourg > Computer Science and Communications Research Unit ; Technical University of Denmark > Department of Applied Mathematics and Computer Science
Venkatesh, Srinivas Vivek ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
External co-authors :
yes
Language :
English
Title :
Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures
Publication date :
2014
Event name :
16th Workshop on Cryptographic Hardware and Embedded Systems – CHES 2014
Event place :
South Korea
Event date :
23-09-2014 to 26-09-2014
Audience :
International
Main work title :
Cryptographic Hardware and Embedded Systems – CHES 2014