On the classification of 4 bit S-boxes. (English) Zbl 1184.94239

Leander, G.; Poschmann, A.

Carlet, Claude (ed.) et al., Arithmetic of finite fields. First international workshop, WAIFI 2007, Madrid, Spain, June 21–22, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73073-6/pbk). Lecture Notes in Computer Science 4547, 159-176 (2007).

Summary: In this paper we classify all optimal 4 bit S-boxes. Remarkably, up to affine equivalence, there are only 16 different optimal S-boxes. This observation can be used to efficiently generate optimal S-boxes fulfilling additional criteria. One result is that an S-box which is optimal against differential and linear attacks is always optimal with respect to algebraic attacks as well. We also classify all optimal S-boxes up to the so called CCZ equivalence. We furthermore generated all S-boxes fulfilling the conditions on nonlinearity and uniformity for S-boxes used in the block cipher Serpent. Up to a slightly modified notion of equivalence, there are only 14 different S-boxes. Due to this small number it is not surprising that some of the S-boxes of the Serpent cipher are linear equivalent. Another advantage of our characterization is that it eases the highly non-trivial task of choosing good S-boxes for hardware dedicated ciphers a lot.
For the entire collection see [Zbl 1121.11002].

MSC:

94A60

Cryptography

Keywords:

S-box; vectorial Boolean function; affine equivalence; hardware implementation