Paper 2016/831

Reducing the Number of Non-linear Multiplications in Masking Schemes

Jürgen Pulkus and Srinivas Vivek

Abstract

In recent years, methods to securely mask S-boxes against side-channel attacks by representing them as polynomials over finite binary fields have become quite efficient. A good cost model for this is to count how many non-linear multiplications are needed. In this work we improve on the current state-of-the-art generic method published by Coron-Roy-Vivek at CHES 2014 by working over slightly larger fields than strictly needed. This leads us, for example, to evaluate DES S-boxes with only 3 non-linear multiplications and, as a result, obtain \(25\%\) improvement in the running time for secure software implementations of DES when using three or more shares. On the theoretical side, we prove a logarithmic upper bound on the number of non-linear multiplications required to evaluate any \(d\)-bit S-box, when ignoring the cost of working in unreasonably large fields. This upper bound is lower than the previous lower bounds proved under the assumption of working over the field \(\mathbb{F}_{2^d}\), and we show this bound to be sharp. We also achieve a way to evaluate the AES S-box using only 3 non-linear multiplications over \(\mathbb{F}_{2^{16}}\).

Note: This is the author accepted manuscript (AAM). The final published version (version of record) is available online via Springer at http://link.springer.com/chapter/10.1007%2F978-3-662-53140-2_23. Please refer to any applicable terms of use of the publisher.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in CHES 2016
DOI
10.1007/978-3-662-53140-2_23
Keywords
side-channel countermeasuremaskingprobing securityblock ciphersoftware implementationpolynomial evaluation
Contact author(s)
Juergen Pulkus @ gi-de com
sv venkatesh @ bristol ac uk
History
2016-08-30: received
Short URL
https://ia.cr/2016/831
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/831,
      author = {Jürgen Pulkus and Srinivas Vivek},
      title = {Reducing the Number of Non-linear Multiplications in Masking Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2016/831},
      year = {2016},
      doi = {10.1007/978-3-662-53140-2_23},
      note = {\url{https://eprint.iacr.org/2016/831}},
      url = {https://eprint.iacr.org/2016/831}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.