Paper 2015/1041 Original: eprint.iacr.org/2015/1041 ↗
The Number of Boolean Functions with Multiplicative Complexity 2
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.
Metadata
- Available format(s)
PDF- Category
- Secret-key cryptography
- Publication info
- Preprint.
- History
- 2016-03-10: last updated
- 2015-10-28: published
- Short URL
- https://ia.cr/2015/1041
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}