Reducing the Number of Non-linear Multiplications in Masking Schemes

Jürgen Pulkus, Srinivas Vivek

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

5 Citations (Scopus)


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 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 F_{2^{16}}.
Original languageEnglish
Title of host publicationCryptographic Hardware and Embedded Systems – CHES 2016
Subtitle of host publication18th International Conference, Santa Barbara, CA, USA, August 17-19, 2016, Proceedings
EditorsBenedikt Gierlichs, Axel Y Poschmann
Number of pages19
ISBN (Electronic)9783662531402
ISBN (Print)9783662531396
Publication statusPublished - 4 Aug 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
ISSN (Print)0302-9743


  • Side-channel countermeasure
  • Masking
  • Probing security
  • Block cipher
  • oftware implementation
  • Polynomial evaluation


Dive into the research topics of 'Reducing the Number of Non-linear Multiplications in Masking Schemes'. Together they form a unique fingerprint.

Cite this