New Bounds on the Multiplicative Complexity of Boolean Functions
Meltem Sonmez Turan
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^k2+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}.
Special issue on Boolean Functions and their Applications in the Journal Cryptography and Communications
September 11-16, 2022
The 7th International Workshop on Boolean Functions and their Applications (BFA)
Sonmez Turan, M.
New Bounds on the Multiplicative Complexity of Boolean Functions, Special issue on Boolean Functions and their Applications in the Journal Cryptography and Communications, Balestrand, NO, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=935024
(Accessed December 7, 2023)