[Resource Topic] 2018/002: The Multiplicative Complexity of 6-variable Boolean Functions

Welcome to the resource topic for 2018/002

The Multiplicative Complexity of 6-variable Boolean Functions

Authors: Cagdas Calik, Meltem Sonmez Turan, Rene Peralta


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.

ePrint: https://eprint.iacr.org/2018/002

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .