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}. This complexity measure is relevant for many advanced cryptographic protocols such as fully homomorphic encryption, multi-party computation,...
See full 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}. This complexity measure is relevant for many advanced cryptographic protocols such as fully homomorphic encryption, multi-party computation, and zero-knowledge proofs, where processing
AND gates is more expensive than processing
XOR gates. Although there is no known asymptotically efficient technique to compute the MC of a random Boolean function, bounds on the MC of Boolean functions are successfully used to to show existence of Boolean functions with a particular MC. In 2000, Boyar et al. showed that, for all
\(n\) ≥ 0, at most
\(2^{k^2+2k+2kn+n+1}\) \(n\)-variable Boolean functions with can be computed with
\(k\) AND gates, This bound is used to prove the existence of a 7-variable Boolean functions with MC greater than 7. In this paper, we improve the Boyar et al. bound by a factor of
\(2^{3k}3^k\).
Hide full abstract
