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
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},
      note = {\url{https://eprint.iacr.org/2015/1041}},
      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.