Cryptology ePrint Archive: Report 2015/1041

The Number of Boolean Functions with Multiplicative Complexity 2

Magnus Gausdal Find and Daniel Smith-Tone and 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.

Category / Keywords: secret-key cryptography / Affine equivalence and Boolean functions and Cryptography and Multiplicative complexity and Self-mappings

Date: received 27 Oct 2015, last revised 10 Mar 2016

Contact author: meltemsturan at gmail com

Available format(s): PDF | BibTeX Citation

Note: We improved the presentation of the results and corrected some mistakes.

Version: 20160310:204542 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]