### 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 studied 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.

Note: see publication info

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. A short 6-page version of this work and a poster was presented at the 2nd IMA conference Mathematics in Defence 2011, UK and included in electronic proceedings. A longer version was presented at SHARCS 2012 workshop in Washington DC.
Keywords
block ciphersnon-linearityalgebraic attackscircuit complexitymultiplicative complexityalgebraic cryptanalysisside-channel attacks
Contact author(s)
n courtois @ cs ucl ac uk
History
2012-04-30: last of 4 revisions
See all versions
Short URL
https://ia.cr/2011/475

CC BY

BibTeX

@misc{cryptoeprint:2011/475,
author = {Nicolas T.  Courtois and Daniel Hulme and Theodosis Mourouzis},
title = {Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis},
howpublished = {Cryptology ePrint Archive, Paper 2011/475},
year = {2011},
note = {\url{https://eprint.iacr.org/2011/475}},
url = {https://eprint.iacr.org/2011/475}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.