Çalık Çağdaş, Turan Meltem Sönmez, Peralta René
National Institute of Standards and Technology.
National Institute of Standards and Technology & Dakota Consulting Inc.
Cryptogr Commun. 2018;11(1):93-107. doi: 10.1007/s12095-018-0297-2.
The multiplicative complexity of a Boolean function is the minimum number of two-input 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. [1] showed that -variable Boolean functions can be implemented with at most -1 AND gates for ≤ 5. A counting argument can be used to show that, for ≥ 7, there exist -variable Boolean functions with multiplicative complexity of at least . In this work, we propose a method to find the multiplicative complexity of Boolean functions by analyzing 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 150357 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.
布尔函数的乘法复杂度是指在（与、异或、非）基上实现该函数所需且足够的双输入与门的最小数量。即使对于输入数量较少的函数，确定给定函数的乘法复杂度在计算上也是难以处理的。图兰等人[1]表明，对于(n\leq5)，(n)变量布尔函数最多可以用(n - 1)个与门实现。通过计数论证可以表明，对于(n\geq7)，存在乘法复杂度至少为(n)的(n)变量布尔函数。在这项工作中，我们提出了一种方法，通过分析具有特定数量与门的电路并利用函数的仿射等价性来确定布尔函数的乘法复杂度。我们使用这种方法研究6变量布尔函数的乘法复杂度，并计算所有150357个仿射等价类的乘法复杂度。我们表明，任何6变量布尔函数最多可以用6个与门实现。此外，我们展示了乘法复杂度为6的特定6变量布尔函数。
