Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

The Number of Boolean Functions with Multiplicative Complexity 2

Published

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

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 May 23, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created October 27, 2015, Updated October 2, 2017