Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis
Nicolas T. Courtois, Daniel Hulme, Theodosis Mourouzis · IACR Cryptology ePrint Archive · 2011
One of the hardest problems in computer science is the prob- lem of gate-e-cient implementation. Such optimizations are particularly important in industrial hardware implementations of standard crypto- graphic algorithms. In this paper we focus on optimizing some small circuits such as S-boxes in cryptographic algorithms. We consider the no- tion of Multiplicative Complexity, a new important notion of complexity introduced in 2008 by Boyar and Peralta and applied to flnd interesting optimizations for the S-box of the AES cipher (13,16,15). We applied this methodology to produce a compact implementation of several ciphers. In this short paper we report our results on PRESENT and GOST, two block ciphers known for their exceptionally low hardware cost. This kind of representation seems to be very promising in implementations aiming at preventing side channel attacks on cryptographic chips such as DPA. More importantly, we postulate that this kind of minimality is also an important and interesting tool in cryptanalysis.