Paper 2022/1077

New Bounds on the Multiplicative Complexity of Boolean Functions

Meltem Sonmez Turan, National Institute of Standards and Technology

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\geq 0$, at most $2^{k^2+2k+2kn+n+1}$ $n$-variable Boolean functions can be computed with $k$ AND gates. This bound is used to prove the existence of a 8-variable Boolean functions with MC greater than 7. In this paper, we improve the Boyar et al. bound.

Note: This work has been accepted to be presented at the 7th International Workshop on Boolean Functions and their Applications (BFA).

Available format(s)
Publication info
Boolean functions Circuit Complexity Multiplicative Complexity
Contact author(s)
meltemsturan @ gmail com
2022-08-25: revised
2022-08-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Meltem Sonmez Turan},
      title = {New Bounds on the Multiplicative Complexity of Boolean Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1077},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.