The Multiplicative Complexity of Boolean Functions on Four and Five Variables
| Autor: | René Peralta, Meltem Sönmez Turan |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783319163628 LightSec |
| DOI: | 10.1007/978-3-319-16363-5_2 |
| Popis: | A generic way to design lightweight cryptographic primitives is to construct simple rounds using small nonlinear components such as 4\(\,\times \,\)4 S-boxes and use these iteratively (e.g., PRESENT [1] and SPONGENT [2]). 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 [3]. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|