Paper 2019/1364

Boolean Functions with Multiplicative Complexity 3 and 4

Cagdas Calik, Meltem Sonmez Turan, and Rene Peralta


Multiplicative complexity (MC) is defined as the minimum number of AND gates required to implement a function with a circuit over the basis (AND, XOR, NOT). Boolean functions with MC 1 and 2 have been characterized in Fischer and Peralta ( 2002) and Find et al. (2017), respectively. In this work, we identify the affine equivalence classes for functions with MC 3 and 4. In order to achieve this, we utilize the notion of the dimension $dim(f)$ of a Boolean function in relation to its linearity dimension, and provide a new lower bound suggesting that multiplicative complexity of $f$ is at least $\ceil{dim(f)/2}$. For MC 3, this implies that there are no equivalence classes other than those $24$ identified in Calik et al (2018). Using the techniques from Calik et al. (2018) and the new relation between dimension and MC, we identify the 1277 equivalence classes having MC 4. We also provide a closed formula for the number of $n$-variable functions with MC 3 and 4. The techniques allow us to construct MC-optimal circuits for Boolean functions that have MC 4 or less, independent of the number of variables they are defined on.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
meltemsturan @ gmail com
cagdascalik @ gmail com
meltem turan @ nist gov
rene peralta @ nist gov
2019-11-27: received
Short URL
Creative Commons Attribution


      author = {Cagdas Calik and Meltem Sonmez Turan and Rene Peralta},
      title = {Boolean Functions with Multiplicative Complexity 3 and 4},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1364},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.