A new method to determine algebraic expression of power mapping based S-boxes

Power mapping based S-boxes, especially those with finite field inversion, have received significant attention by cryptographers. S-boxes designed by finite field inversion provide good cryptographic properties and are used in most ciphersʼ design such as Advanced Encryption Standard (AES), Camellia, Shark and others. However, such an S-box consists of a simple algebraic expression, thus the S-box design is completed by adding an affine transformation before the input of the S-box, or after the output of the S-box or both in order to make the overall S-box description more complex in a finite field.In the present study, a new method of computation of the algebraic expression (as a polynomial function over GF(28)GF(28)) of power mapping based S-boxes designed by three different probable cases is described in which the place of the affine transformation differs. The proposed method is compared with the Lagrange interpolation formula with respect to the number of polynomial operations needed. The new method (based on the square-and-multiply technique) is found to reduce time and polynomial operation complexity in the computation of the algebraic expression of S-boxes.

► We propose a new method for computing the algebraic expression of power mapping based S-boxes.
► We compare our method with Lagrange interpolation formula.
► The proposed method reduces time and polynomial operation complexity in the computation of algebraic expression of S-boxes.
► The proposed method provides the reason why AES S-box algebraic expression includes sparse number of terms.