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 April 23, 2024)
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)
, ,
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
Pub Type
Websites
Download Paper
Keywords
Affine equivalence, Boolean functions, Cryptography, Multiplicative complexity, Self-mappings
Citation
Created October 27, 2015, Updated October 2, 2017