Paper 2006/322

Algebraic Immunity of S-boxes Based on Power Mappings: Analysis and Construction

Yassir Nawaz, Kishan Chand Gupta, and Guang Gong


The algebraic immunity of an S-box depends on the number and type of linearly independent multivariate equations it satisfies. In this paper techniques are developed to find the number of linearly independent, multivariate, bi-affine and quadratic equations for S-boxes based on power mappings. These techniques can be used to prove the exact number of equations for any class of power mappings. Two algorithms to calculate the number of bi-affine and quadratic equations for any $(n,n)$ S-box based on power mapping are also presented. The time complexity of both algorithms is only $O(n^2)$. To design algebraically immune S-boxes four new classes of S-boxes that guarantee zero bi-affine equations and one class of S-boxes that guarantees zero quadratic equations are presented. The algebraic immunity of power mappings based on Kasami, Niho, Dobbertin, Gold, Welch and Inverse exponents are discussed along with other cryptographic properties and several cryptographically strong S-boxes are identified. It is conjectured that a known Kasami like APN power mapping is maximally nonlinear and a known Kasami like maximally nonlinear power mapping is differentially 4-uniform. Finally an open problem to find an $(n,n)$ bijective nonlinear S-box with more than $5n$ quadratic equations is solved and it is conjectured that the upper bound on this number is $\frac{n(n-1)}{2}$.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
ynawaz @ engmail uwaterloo ca
2006-09-26: received
Short URL
Creative Commons Attribution


      author = {Yassir Nawaz and Kishan Chand Gupta and Guang Gong},
      title = {Algebraic Immunity of S-boxes Based on Power Mappings: Analysis and Construction},
      howpublished = {Cryptology ePrint Archive, Paper 2006/322},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.