Cryptology ePrint Archive: Report 2015/848

The Multiplicative Complexity of Boolean Functions on Four and Five Variables

Meltem Sonmez Turan and Rene 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, efficient 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 65 536 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 show that the multiplicative complexity of a Boolean function with five variables is at most four.

Category / Keywords: secret-key cryptography / Affine transformation and Boolean functions and Circuit complexity and Multiplicative Complexity

Original Publication (in the same form): LightSec 2014

Date: received 1 Sep 2015

Contact author: meltemsturan at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150902:132538 (All versions of this report)

Short URL: ia.cr/2015/848

Discussion forum: Show discussion | Start new discussion