The Number of Boolean Functions with Multiplicative Complexity 2

Published

October 27, 2015

Author(s)

Magnus G. Find, Daniel C. Smith-Tone, Meltem Sonmez Turan

Abstract

Multiplicative complexity is a complexity measure, which is defined as the minimum number of AND gates required to implement a given primitive by a circuit over the basis (AND, XOR, NOT), with an unlimited number of NOT and XOR gates. 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^{n+1}\binom{2^n-1}{2}$. 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.

Citation

IACR ePrint

Volume

2015

Pub Weblink

http://ia.cr/2015/1041

Pub Type

Websites

Download Paper

Local Download

Keywords

Affine equivalence, Boolean functions, Cryptography, Multiplicative complexity, Self-mappings

Citation

Find, M. , Smith-Tone, D. and Sonmez, M. (2015), The Number of Boolean Functions with Multiplicative Complexity 2, IACR ePrint, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=919209, http://ia.cr/2015/1041 (Accessed October 13, 2025)