Paper 2015/848 Original: eprint.iacr.org/2015/848 ↗
The Multiplicative Complexity of Boolean Functions on Four and Five Variables
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.
Metadata
- Available format(s)
PDF- Category
- Secret-key cryptography
- Publication info
- Preprint.
- History
- 2015-09-02: last updated
- 2015-09-02: published
- Short URL
- https://ia.cr/2015/848
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2015/848,
author = {Meltem Sonmez Turan and Rene Peralta},
title = {The Multiplicative Complexity of Boolean Functions on Four and Five Variables},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/848},
year = {2015},
url = {https://eprint.iacr.org/2015/848}
}