Boolean Functions with Multiplicative Complexity 3 and 4

Published

July 18, 2020

Author(s)

Cagdas Calik, Meltem Sonmez Turan, Rene C. Peralta

Abstract

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.

Citation

Cryptography and Communication

Pub Type

Journals

Download Paper

https://doi.org/10.1007/s12095-020-00445-z

Local Download

Keywords

Affine equivalence, Boolean functions, Multiplicative Complexity

Citation

Calik, C. , Sonmez, M. and Peralta, R. (2020), Boolean Functions with Multiplicative Complexity 3 and 4, Cryptography and Communication, [online], https://doi.org/10.1007/s12095-020-00445-z (Accessed April 26, 2026)

Additional citation formats