**Boolean Functions with Multiplicative Complexity 3 and 4**

*Cagdas Calik and Meltem Sonmez Turan and Rene 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 ( 2002) and Find et al. (2017), 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 those $24$ identified in Calik et al (2018). Using the techniques from Calik et al. (2018) 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.

**Category / Keywords: **implementation / Affine equivalence and Boolean functions and Multiplicative complexity

**Date: **received 26 Nov 2019

**Contact author: **meltemsturan at gmail com, cagdascalik at gmail com, meltem turan at nist gov, rene peralta at nist gov

**Available format(s): **PDF | BibTeX Citation

**Version: **20191127:081746 (All versions of this report)

**Short URL: **ia.cr/2019/1364

[ Cryptology ePrint archive ]