Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures
verfasst von : Jean-Sébastien Coron, Arnab Roy, Srinivas Vivek
Erschienen in: Cryptographic Hardware and Embedded Systems – CHES 2014
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.