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


Received 28 March 2004
Revised manuscript received 9 July 2004


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.