The number of Boolean functions with multiplicative complexity 2 (Q725955)

Summary: 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, multiparty computation and zero-knowledge proofs. \textit{M. J. Fischer} and \textit{R. Peralta} [``Counting Predicates of Conjunctive Complexity One'', Yale TR-1222, (2002)] computed the number of \(n\)-variable Boolean functions with multiplicative complexity 1. In this paper, we study Boolean functions that can be constructed with two AND gates. By characterising 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.