The multiplicative complexity of 6-variable Boolean functions

• Published in: Cryptography and communications 2019-01, Vol.11 (1), p.93-107
• Main Authors: Çalık, Çağdaş, Sönmez Turan, Meltem, Peralta, René
• Format: Article
• Language: English
• Subjects: Affine transformations; Boolean algebra; Boolean functions; Boolean Functions and their Applications II; Circuits; Codes; Coding and Information Theory; Communications Engineering; Complexity; Computer Science; Data Structures and Information Theory; Equivalence; Gates; Information and Communication; Mathematical analysis; Mathematics of Computing; Networks
• ISSN: 1936-2447; 1936-2455
• DOI: 10.1007/s12095-018-0297-2

The multiplicative complexity of a Boolean function is the minimum number of two-input 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. [ 1 ] showed that n -variable Boolean functions can be implemented with at most n − 1 AND gates for n ≤ 5 . A counting argument can be used to show that, for n ≥ 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 150 357 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.