Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

The Multiplicative Complexity of 6-variable Boolean Functions

Published

Author(s)

Cagdas Calik, Meltem Sonmez Turan, Rene C. 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. \cite{TuranSonmez2015} 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 exists $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 all 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.
Citation
Cryptography and Communication

Keywords

Affine equivalence , Boolean functions , Circuit complexity , Cryptography , Multiplicative complexity

Citation

Calik, C. , Sonmez, M. and Peralta, R. (2018), The Multiplicative Complexity of 6-variable Boolean Functions, Cryptography and Communication, [online], https://doi.org/10.1007/s12095-018-0297-2 (Accessed April 24, 2024)
Created April 3, 2018, Updated November 10, 2018