Paper 2018/002

The Multiplicative Complexity of 6-variable Boolean Functions

Cagdas Calik, Meltem Sonmez Turan, and Rene Peralta

Abstract

The multiplicative complexity of a Boolean function is the minimum number of AND gates that are necessary and sufficient to implement the function over the basis (AND, XOR, NOT). Finding the multiplicative complexity of a given function is computationally intractable, even for functions with small number of inputs. Turan et al. showed that $n$-variable Boolean functions can be implemented with at most $n-1$ AND gates for $n\leq 5$. A counting argument can be used to show that, for $n \geq 7$, there exist $n$-variable Boolean functions with multiplicative complexity of at least $n$. In this work, we propose a method to find the multiplicative complexity of Boolean functions by analyzing circuits with a particular number of AND gates and utilizing the affine equivalence of functions. We use this method to study the multiplicative complexity of 6-variable Boolean functions, and calculate the multiplicative complexities of all 150357 affine equivalence classes. We show that any 6-variable Boolean function can be implemented using at most 6 AND gates. Additionally, we exhibit specific 6-variable Boolean functions which have multiplicative complexity 6.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
meltemsturan @ gmail com
History
2018-01-02: received
Short URL
https://ia.cr/2018/002
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/002,
      author = {Cagdas Calik and Meltem Sonmez Turan and Rene Peralta},
      title = {The Multiplicative Complexity of 6-variable Boolean Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/002},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/002}},
      url = {https://eprint.iacr.org/2018/002}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.