An Algorithm for Improving Algebraic Degree of S-Box Coordinate Boolean Functions Based on Affine Equivalence Transformation

Hoang Duc Tho, Nguyen Truong Thang, Nguyen Thi Thu Nga, Pham Quoc Hoang


The Substitution box (\(S\)-box) plays an important role in a block cipher as it is the only  nonlinear part of the cipher in most cases.  \(S\)-box \(S\) can be considered as a vectorial Boolean function consisting of \(m\) individual Boolean functions \(f_1,f_2,\dots,f_m\), where \(f_i: GF (2^n)\to GF (2)\) and \( f_i(x)=y_i\) for \(i=1,2,\dots,m\). These functions  are called coordinate Boolean functions of the \(S\)-box \(S\). To avoid various attacks on the ciphers and for efficient software implementation, the coordinate Boolean functions of \(S\)-boxes are required to satisfy a lot of properties, for instance being a permutation defined on the fields with even degrees, with a high nonlinearity, a low differential uniformity and a high algebraic degree, etc. However, it seems very difficult to find an \(S\)-box with the coordinate Boolean functions to satisfy all the criteria. The \(S\)-box with low algebraic degree of the coordinate Boolean functions is vulnerable to many attacks such as linear and differential cryptanalysis, for instance higher-order differential attacks, algebraic attacks or cube attacks. In this paper we propose an algorithm for improving algebraic degree of the $S$-box coordinate Boolean functions while not affecting its other important properties. The algorithm is based on affine equivalence transformation of the \(S\)-boxes.


S-boxes; Affine equivalence; Algebraic degree

Full Text:



A. Biryukov, C. De Canniere, A. Braeken and B. Preneel, A toolbox for cryptanalysis: Linear and affine equivalence algorithms, InInternational Conference on the Theory and Applications of Cryptographic Techniques, Springer, Berlin — Heidelberg, pp. 33-50 (May, 2003).

A. Bogdanov, L.R. Knudsen, G. Leander, C. Paar, A. Poschmann, M.J. Robshaw and C. Vikkelsoe, PRESENT: An ultra-lightweight block cipher, in International Workshop on Cryptographic Hardware and Embedded Systems (pp. 450-466), Springer, Berlin — Heidelberg (2007, September).

N.P. Borisenko and H.D. Tho, Algorithms for minimization of the number of logic elements in a circuit implementing S-box Boolean functions, in Proceedings of 3rd Workshop on Current Trends in Cryptology (CTCrypt’2014), Moscow, Russia (2014).

C. Boura and A. Canteaut, On the influence of the algebraic degree of on the algebraic degree of. IEEE Transactions on Information Theory 59(1) (2013), 691 – 702.

C. Boura, A. Canteaut and C. De Canniere, Higher-order differential properties of Keccak and Luffa, in International Workshop on Fast Software Encryption (pp. 252-269), Springer, Berlin — Heidelberg (February, 2011).

C. Carlet, Boolean functions for cryptography and error correcting codes, Boolean Models and Methods in Mathematics, Computer Science, and Engineering 2 (2010), 257.

Y. Crama and P.L. Hammer, Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Vol. 2), Cambridge University Press (2010).

T.W. Cusick and P. Stanica„ Cryptographic Boolean Functions and Applications, Academic Press (2009).

J. Daemen and V. Rijmen, The Design of Rijndael: AES — the Advanced Encryption Standard, Springer Science & Business Media (2013).

L.T. Dung and H.D. Tho, An algorithm for improving algebraic degree of S-box based on affine equivalence transformation, International Journal of Knowledge and Systems Science 8(1) (2017), 53 – 64.

A. Grocholewska-Czuryło, Cryptographic properties of modified AES-like S-boxes, Annales UMCS, Informatica 11(2) (January, 2011), 37 – 48.

G. Ivanov, N. Nikolov and S. Nikova, Reversed genetic algorithms for generation of bijective S-boxes with good cryptographic properties, Cryptography and Communications 8(2) (2016), 247 – 276.

G. Leander and A. Poschmann, On the classification of 4 bit S-boxes, in: International Workshop on the Arithmetic of Finite Fields, pp. 159-176, Springer, Berlin — Heidelberg (June, 2007).

J. McLaughlin and J.A. Clark, Using evolutionary computation to create vectorial Boolean functions with low differential uniformity and high nonlinearity, arXiv preprint arXiv:1301.6972 (2013).

National Institute for Science and Technology (NIST), Advanced Encryption Standard (AES), URL: (November, 2001).

National Institute for Science andTechnology (NIST), Data Encryption Standard (DES), URL: (October, 1999).

B. Preneel and A. Braeken, Cryptographic Properties of Boolean Functions and S-Boxes (2006).

A.G. Rostovtsev and E.B. Mahovenko, Theoretical cryptography, St. Petersburg Press (in Russian) (2005).

C.E. Shannon, Communication theory of secrecy systems, Bell System Technical Journal 28(4) (1949), 656 – 715.

Y. Tan, G. Gong and B. Zhu, Enhanced criteria on differential uniformity and nonlinearity of cryptographically significant functions, Cryptography and Communications 8(2) (2016), 291 – 311.


eISSN 0975-5748; pISSN 0974-875X