“Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis”

Recently, Nicolas Courtois sent me a revised version of my PRESENT bitslice implementation which improves the representation of the S-Box and hence the performance considerably. A paper describing the techniques used to arrive at this new S-box representation is now available on eprint:

Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis

Nicolas T. Courtois, Daniel Hulme and Theodosis Mourouzis

Abstract: One of the hardest problems in computer science is the problem of gate-eficient implementation. Such optimizations are particularly important in industrial hardware implementations of standard cryptographic algorithms. In this paper we focus on optimizing some small circuits such as S-boxes in cryptographic algorithms. We consider the notion of Multiplicative Complexity, a new important notion of complexity introduced in 2008 by Boyar and Peralta and applied to find interesting optimizations for the S-box of the AES cipher. 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.

One thought on ““Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis”

  1. Interesting. Actually, there has been some work done on the DES S-box, and it was (is?) a nice trial-and-effort work. Mostly hackers (=fun, sometimes fringe people, not the ‘bad guys’) worked on the problem, which tells you how much scientific value some see in this sort of thing. However, it’s pretty important in some fields, for example, electronic engineering, and thus, SAT. I have in fact entertained some thoughts about doing this sort of simplification in an organised way. SAT solvers could do this, but the idea of describing meta-circuits in CNF has always given me a headache before I even began, so I didn’t. It’s nice to see someone taking the challenge (though, again, talking about unfortunately ‘fringe’ science, it may not be an accident who did it). The really interesting thing about this problem is that these sort of gate-minimisations were the norm in the early days of electronic engineering. Maybe some relatively old (over 60 maybe) electric engineers could teach us some important aspects of this problem. I wish I had access to one.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s