Published: March 17, 2015
Author(s)
Meltem Sönmez Turan (NIST), Rene Peralta (NIST)
Conference
Name: Third International Workshop on Lightweight Cryptography for Security and Privacy (LightSec 2014)
Dates: 09/01/2014 - 09/02/2014
Location: Istanbul, Turkey
Citation: Lightweight Cryptography for Security and Privacy, vol. 8898, pp. 21-33
A generic way to design lightweight cryptographic primitives is to construct simple rounds using small nonlinear components such as 4 × 4 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 65536 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.
A generic way to design lightweight cryptographic primitives is to construct simple rounds using small nonlinear components such as 4 × 4 S-boxes and use these iteratively (e.g., PRESENT and SPONGENT). In order to efficiently implement the primitive, efficient implementations of its internal...
See full abstract
A generic way to design lightweight cryptographic primitives is to construct simple rounds using small nonlinear components such as 4 × 4 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 65536 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.
Hide full abstract
Keywords
affine transformation; Boolean functions; circuit complexity; multiplicative complexity
Control Families
None selected
