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.

Boolean Functions with Multiplicative Complexity 3 and 4



Cagdas Calik, Meltem Sonmez Turan, Rene C. Peralta


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, and Find et al., 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 the $24$ identified in Calik et al. Using the techniques from Calik et al. 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.
Cryptography and Communication


Affine equivalence, Boolean functions, Multiplicative Complexity


Calik, C. , Sonmez, M. and Peralta, R. (2020), Boolean Functions with Multiplicative Complexity 3 and 4, Cryptography and Communication, [online], (Accessed June 14, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created July 17, 2020, Updated July 27, 2020