Boolean Functions with Multiplicative Complexity 3 and 4

Cagdas Calik; Meltem Sonmez Turan; Rene Peralta

Paper 2019/1364

Boolean Functions with Multiplicative Complexity 3 and 4

Cagdas Calik, Meltem Sonmez Turan, and Rene Peralta

Abstract

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.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint. MINOR revision.
Contact author(s): meltemsturan @ gmail com
cagdascalik @ gmail com
meltem turan @ nist gov
rene peralta @ nist gov
History: 2019-11-27: received
Short URL: https://ia.cr/2019/1364
License: CC BY

BibTeX

@misc{cryptoeprint:2019/1364,
      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},
      url = {https://eprint.iacr.org/2019/1364}
}