Multiplicative complexity is a complexity measure, which is defined as the minimum number of AND gates required to implement a given primitive by a circuit over the basis (AND, XOR, NOT), with an unlimited number of NOT and XOR gates. 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^{n+1}\binom{2^n-1}{2}$. 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.
Multiplicative complexity is a complexity measure, which is defined as the minimum number of AND gates required to implement a given primitive by a circuit over the basis (AND, XOR, NOT), with an unlimited number of NOT and XOR gates. Implementations of ciphers with a small number of AND gates are...
See full abstract
Multiplicative complexity is a complexity measure, which is defined as the minimum number of AND gates required to implement a given primitive by a circuit over the basis (AND, XOR, NOT), with an unlimited number of NOT and XOR gates. 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^{n+1}\binom{2^n-1}{2}$. 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.
Hide full abstract
