Paper 2016/557

On the Multiplicative Complexity of Boolean Functions and Bitsliced Higher-Order Masking

Dahmun Goudarzi and Matthieu Rivain


Higher-order masking is a widely used countermeasure to make software implementations of blockciphers achieve high security levels against side-channel attacks. Unfortunately, it often comes with a strong impact in terms of performances which may be prohibitive in some contexts. This situation has motivated the research for efficient schemes that apply higher-order masking with minimal performance overheads. The most widely used approach is based on a polynomial representation of the cipher s-box(es) allowing the application of standard higher-order masking building blocks such as the ISW scheme (Ishai-Sahai-Wagner, Crypto 2003). Recently, an alternative approach has been considered which is based on a bitslicing of the s-boxes. This approach has been shown to enjoy important efficiency benefits, but it has only been applied to specific blockciphers such as AES, PRESENT, or custom designs. In this paper, we present a generic method to find a Boolean representation of an s-box with efficient bitsliced higher-order masking. Specifically, we propose a method to construct a circuit with low \emph{multiplicative complexity}. Compared to previous work on this subject, our method can be applied to any s-box of common size and not necessarily to small s-boxes. We use it to derive higher-order masked s-box implementations that achieve important performance gain compared to optimized state-of-the-art implementations.

Available format(s)
Publication info
A minor revision of an IACR publication in CHES 2016
Higher-Order MaskingBoolean FunctionsMultiplicative ComplexityBitsliceSide-Channel Countermeasures
Contact author(s)
matthieu rivain @ gmail com
2017-02-08: last of 2 revisions
2016-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dahmun Goudarzi and Matthieu Rivain},
      title = {On the Multiplicative Complexity of Boolean Functions and Bitsliced Higher-Order Masking},
      howpublished = {Cryptology ePrint Archive, Paper 2016/557},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.