New Generation Computing, 23(2005)219-231
Ohmsha, Ltd. and Springer

The Design of S-Boxes by Simulated Annealing

John A. Clark, Jeremy L. Jacob, Susan Stepney
Department of Computer Science, University of York
Heslington, York, YO10 5DD, UK
{jac,jeremy,susan}@cs.york.ac.uk

Received 28 March 2004
Revised manuscript received 9 July 2004

Abstract

Substitution boxes (S-boxes) are important components in many modern-day symmetric key ciphers. Their study has attracted a great deal of attention over many years. The emergence of a variety of cryptosystem attacks has shown that substitutions must be designed with great care. Some general criteria such as high non-linearity and low autocorrelation have been proposed (providing some protection against attacks such as linear cryptanalysis and differential cryptanalysis). The design of appropriate S-boxes is a difficult task; several criteria must be traded off and the design space is huge. There has been little application of evolutionary search to the development of S-boxes. In this paper we show how a cost function that has found excellent single-output Boolean functions can be generalized to provide improved results for small S-boxes.

Keywords:Cryptography, S-boxes, Nonlinearity, Autocorrelation, Simulated Anneal.

[Back]