Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Biham, E., Shamir, A.: Differential cryptanalysis of des-like cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1990)
Biryukov, A., De Cannière, C., Braeken, A., Preneel, B.: A toolbox for cryptanalysis: Linear and affine equivalence algorithms. In: Biham, E. (ed.) Advances in Cryptology – EUROCRPYT 2003. LNCS, vol. 2656, pp. 33–50. Springer, Heidelberg (2003)
Brinkman, M., Leander, G.: On the classification of apn functions up to dimension five. International Workshop on Coding and Cryptography (2007)
Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for des-like cryptosystems. Des. Codes Cryptography 15(2), 125–156 (1998)
Courtois, N., Pieprzyk, J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002)
Courtois, N., Pieprzyk, J.: Cryptanalysis of block ciphers with overdefined systems of equations. Cryptology ePrint Archive, Report 2002/044 (2002), http://eprint.iacr.org/
Knudsen, L.: private communication
Lachaud, G., Wolfmann, J.: The weights of the orthogonals of the extended quadratic binary goppa codes. IEEE Transactions on Information Theory 36(3), 686 (1990)
Lorens, C.S.: Invertible boolean functions. IEEE Trans. Electronic Computers 13(5), 529–541 (1964)
Matsui, M.: Linear cryptoanalysis method for des cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1993)
Nyberg, K.: Perfect nonlinear s-boxes. In: EUROCRYPT 1991. LNCS, vol. 547, pp. 378–386. Springer, Heidelberg (1991)
Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994)
Rothaus, O.S.: On ”bent” functions. J. Comb. Theory, Ser. A 20(3), 300–305 (1976)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Leander, G., Poschmann, A. (2007). On the Classification of 4 Bit S-Boxes. In: Carlet, C., Sunar, B. (eds) Arithmetic of Finite Fields. WAIFI 2007. Lecture Notes in Computer Science, vol 4547. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73074-3_13
Download citation
DOI: https://doi.org/10.1007/978-3-540-73074-3_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73073-6
Online ISBN: 978-3-540-73074-3
eBook Packages: Computer ScienceComputer Science (R0)