Çalık Çağdaş, Turan Meltem Sönmez, Peralta René
NIST Computer Security Division, 100 Bureau Dr, Gaithersburg, MD 20899.
Cryptogr Commun. 2020;12. doi: 10.1007/s12095-020-00445-z.
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 () of a Boolean function in relation to its linearity dimension, and provide a new lower bound suggesting that the multiplicative complexity of is at least [()/2]. For MC 3, this implies that there are no equivalence classes other than those 24 identified in Çalık et al. (2018). Using the techniques from Çalık et al. and the new relation between the dimension and MC, we identify all 1277 equivalence classes having MC 4. We also provide a closed formula for the number of -variable functions with MC 3 and 4. These results allow us to construct AND-optimal circuits for Boolean functions that have MC 4 or less, independent of the number of variables they are defined on.
乘法复杂度（MC）被定义为在（与门、异或门、非门）基础上用电路实现一个函数所需与门的最小数量。乘法复杂度为1和2的布尔函数已分别在费舍尔和佩拉尔塔（2002年）以及芬德等人（2017年）的研究中得到了刻画。在这项工作中，我们确定了乘法复杂度为3和4的函数的仿射等价类。为了实现这一点，我们利用布尔函数关于其线性维度的维度（）概念，并给出一个新的下界，表明 的乘法复杂度至少为[()/2]。对于乘法复杂度为3的情况，这意味着除了在恰利克等人（2018年）中确定的24个等价类之外没有其他等价类。利用恰利克等人的技术以及维度与乘法复杂度之间的新关系，我们确定了所有1277个乘法复杂度为4的等价类。我们还给出了乘法复杂度为3和4的 变量函数数量的封闭公式。这些结果使我们能够为乘法复杂度为4及以下的布尔函数构建与门最优电路，而与它们所定义的变量数量无关。
