Title: The number of boolean functions with multiplicative complexity 2

Authors: Magnus Gausdal Find; Daniel Smith-Tone; Meltem Sönmez Turan

Addresses: Cryptographic Technology Group, National Institute of Standards and Technology, 100 Bureau Dr. Gaithersburg, Gaithersburg, MD 20899, USA ' Cryptographic Technology Group, National Institute of Standards and Technology, 100 Bureau Dr. Gaithersburg, Gaithersburg, MD 20899, USA; University of Louisville, Louisville, KY, USA ' Cryptographic Technology Group, National Institute of Standards and Technology, 100 Bureau Dr. Gaithersburg, Gaithersburg, MD 20899, USA

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.

Keywords: affine transformations; Boolean circuits; circuit complexity; cryptography.

DOI: 10.1504/IJICOT.2017.086890

International Journal of Information and Coding Theory, 2017 Vol.4 No.4, pp.222 - 236

Received: 07 Oct 2016
Accepted: 02 Nov 2016
Published online: 02 Oct 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article