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 Multiplicative Complexity of Boolean Functions on Four and Five Variables

Published

Author(s)

Meltem Sonmez Turan, Rene C. Peralta

Abstract

A generic way to design lightweight cryptographic primitives is to construct simple rounds using small nonlinear components such as 4x4 S-boxes and use these iteratively (e.g., PRESENT and SPONGENT). In order to efficiently implement the primitive, optimal implementations of its internal components are needed. Multiplicative complexity of a function is the minimum number of AND gates required to implement it by a circuit over the basis (AND, XOR, NOT). It is known that multiplicative complexity is exponential in the number of input bits $n$. Thus it came as a surprise that circuits for all 65536 functions on four bits were found which used at most three AND gates. In this paper, we verify this result and extend it to five-variable Boolean functions. We prove that the multiplicative complexity of a Boolean function with five variables is at most four.
Proceedings Title
Lightweight Cryptography for Security and Privacy (Lecture Notes in Computer Science)
Conference Dates
September 1-2, 2014
Conference Location
Istanbul
Conference Title
Third International Workshop on Lightweight Cryptography for Security & Privacy

Keywords

Affine transformation, Boolean functions, Circuit complexity, Multiplicative complexity

Citation

Sonmez, M. and Peralta, R. (2015), The Multiplicative Complexity of Boolean Functions on Four and Five Variables, Lightweight Cryptography for Security and Privacy (Lecture Notes in Computer Science), Istanbul, -1, [online], https://doi.org/10.1007/978-3-319-16363-5_2 (Accessed April 24, 2024)
Created March 17, 2015, Updated November 10, 2018