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(2n3). 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.