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.

New Bounds on the Multiplicative Complexity of Boolean Functions

Published

Author(s)

Meltem Sonmez Turan

Abstract

Multiplicative Complexity (MC) is defined as the minimum number of AND gates required to implement a function with a circuit over the basis AND, XOR, NOT}. This complexity measure is relevant for many advanced cryptographic protocols such as fully homomorphic encryption, multi-party computation, and zero-knowledge proofs, where processing AND gates is more expensive than processing XOR gates. Although there is no known asymptotically efficient technique to compute the MC of a random Boolean function, bounds on the MC of Boolean functions are successfully used to to show existence of Boolean functions with a particular MC. In 2000, Boyar et al. [1] showed that, for all n ≥ 0, at most 2^k2+2k+2kn+n+1} n-variable Boolean functions with can be computed with k AND gates, This bound is used to prove the existence of a 7-variable Boolean functions with MC greater than 7. In this paper, we improve the Boyar et al. bound by a factor of 2^3k}3^k}.
Proceedings Title
Special issue on Boolean Functions and their Applications in the Journal Cryptography and Communications
Conference Dates
September 11-16, 2022
Conference Location
Balestrand, NO
Conference Title
The 7th International Workshop on Boolean Functions and their Applications (BFA)

Keywords

Boolean functions, multiplicative complexity

Citation

Sonmez Turan, M. (2022), New Bounds on the Multiplicative Complexity of Boolean Functions, Special issue on Boolean Functions and their Applications in the Journal Cryptography and Communications, Balestrand, NO, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=935024 (Accessed March 28, 2024)
Created September 11, 2022, Updated December 14, 2022