The Number of Boolean Functions with Multiplicative Complexity 2

Magnus Gausdal Find; Daniel Smith-Tone; Meltem Sonmez Turan

Paper 2015/1041

The Number of Boolean Functions with Multiplicative Complexity 2

Magnus Gausdal Find, 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.

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

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint. MINOR revision.
Contact author(s): meltemsturan @ gmail com
History: 2016-03-10: revised; 2015-10-28: received; See all versions
Short URL: https://ia.cr/2015/1041
License: CC BY

BibTeX

@misc{cryptoeprint:2015/1041,
      author = {Magnus Gausdal Find and Daniel Smith-Tone and Meltem Sonmez Turan},
      title = {The Number of Boolean Functions with Multiplicative Complexity 2},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/1041},
      year = {2015},
      url = {https://eprint.iacr.org/2015/1041}
}