The number of boolean functions with multiplicative complexity 2

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 cyphers with a small number of AND gates are preferred in protocols for fully homomorphic encryption, multiparty computation and zero-knowledge proofs. Fischer and Peralta (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.