Paper 2016/831

Reducing the Number of Non-linear Multiplications in Masking Schemes

Jürgen Pulkus and Srinivas Vivek


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 Please refer to any applicable terms of use of the publisher.

Available format(s)
Publication info
Published by the IACR in CHES 2016
side-channel countermeasuremaskingprobing securityblock ciphersoftware implementationpolynomial evaluation
Contact author(s)
Juergen Pulkus @ gi-de com
sv venkatesh @ bristol ac uk
2016-08-30: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.