Paper 2015/848

The Multiplicative Complexity of Boolean Functions on Four and Five Variables

Meltem Sonmez Turan and Rene Peralta


A generic way to design lightweight cryptographic primitives is to construct simple rounds using small nonlinear components such as 4x4 S-boxes and use these iteratively (e.g., PRESENT and SPONGENT). In order to efficiently implement the primitive, efficient implementations of its internal components are needed. Multiplicative complexity of a function is the minimum number of AND gates required to implement it by a circuit over the basis (AND, XOR, NOT). It is known that multiplicative complexity is exponential in the number of input bits n. Thus it came as a surprise that circuits for all 65 536 functions on four bits were found which used at most three AND gates. In this paper, we verify this result and extend it to five-variable Boolean functions. We show that the multiplicative complexity of a Boolean function with five variables is at most four.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. LightSec 2014
Contact author(s)
meltemsturan @ gmail com
2015-09-02: received
Short URL
Creative Commons Attribution


      author = {Meltem Sonmez Turan and Rene Peralta},
      title = {The Multiplicative Complexity of Boolean Functions on Four and Five Variables},
      howpublished = {Cryptology ePrint Archive, Paper 2015/848},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.