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

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. To avoid various attacks on the ciphers and for efficient software implementation, 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 algebraic degree, a low differential uniformity and a high nonlinearity, etc. However, it seems very difficult to find an S-box to satisfy all the criteria. The S-box of low algebraic degree 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 the authors propose an algorithm for improving algebraic degree of the S-box while not affecting its other important properties. The algorithm is based on affine equivalence transformation of the S-boxes.