Welcome to the resource topic for 2015/1041
Title:
The Number of Boolean Functions with Multiplicative Complexity 2
Authors: Magnus Gausdal Find, Daniel Smith-Tone, Meltem Sonmez Turan
Abstract:Multiplicative complexity is a complexity measure defined as the minimum number of AND gates required to implement a given primitive by a circuit over the basis (AND, XOR, NOT). Implementations of ciphers with a small number of AND gates are preferred in protocols for fully homomorphic encryption, multi-party computation and zero-knowledge proofs. In 2002, Fischer and Peralta showed that the number of n-variable Boolean functions with multiplicative complexity one equals 2\binom{2^n}{3}. In this paper, we study Boolean functions with multiplicative complexity 2. By characterizing the structure of these functions in terms of affine equivalence relations, we provide a closed form formula for the number of Boolean functions with multiplicative complexity 2.
ePrint: https://eprint.iacr.org/2015/1041
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 .