A Non-Linear/Linear Instruction Set Extension for Lightweight Ciphers

Modern cryptography today is substantially involved with securing lightweight (and pervasive) devices. For this purpose, several lightweight cryptographic algorithms have already been proposed. Up to now, the literature has focused on hardware-efficiency while lightweight with respect to software has barely been addressed. However, a large percentage of lightweight ciphers will be implemented on embedded CPUs- without support for cryptographic operations. In parallel, many lightweight ciphers are based on operations which are hardware-friendly but quite costly in software. For instance, bit permutations that accrue essentially no costs in hardware require a non-trivial number of CPU cycles and/or lookup tables in software. Similarly, S-Boxes often require relatively large lookup tables in software. In this work, we try to address the open question of efficient cipher implementations on small CPUs by introducing a non-linear/linear instruction set extension, to which we refer to as NLU, capable of implementing on-linear operations expressed in their algebraic normal form(ANF) and linear operations expressed in binary "matrix multiply-and-add" form. The proposed NLU is targeted for embedded micro controllers and it is therefore 8-bit wide. However, its modular architecture allows it to be used in16, 32, 64 and even 4-bit CPUs. We furthermore present examples of the use of NLU in the implementation of standard cryptographic algorithms in order to demonstrate its coding advantage.