[Resource Topic] 2006/322: Algebraic Immunity of S-boxes Based on Power Mappings: Analysis and Construction

Welcome to the resource topic for 2006/322

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

Authors: Yassir Nawaz, Kishan Chand Gupta, 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}.

ePrint: https://eprint.iacr.org/2006/322

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .