Welcome to the resource topic for 2022/1077
Title:
New Bounds on the Multiplicative Complexity of Boolean Functions
Authors: Meltem Sonmez Turan
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\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.
ePrint: https://eprint.iacr.org/2022/1077
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .