Paper 2022/1077
New Bounds on the Multiplicative Complexity of Boolean Functions
, National Institute of Standards and TechnologyAbstract
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).
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Boolean functions Circuit Complexity Multiplicative Complexity
- Contact author(s)
- meltemsturan @ gmail com
- History
- 2022-08-25: revised
- 2022-08-19: received
- See all versions
- Short URL
- https://ia.cr/2022/1077
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1077,
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{https://eprint.iacr.org/2022/1077}},
url = {https://eprint.iacr.org/2022/1077}
}
