The Multiplicative Complexity of Boolean Functions on Four and Five Variables

Published

March 17, 2015

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

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-319-16363-5_2

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 January 19, 2025)