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

*Yassir Nawaz and Kishan Chand Gupta and Guang Gong*

**Abstract: **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}$.

**Category / Keywords: **secret-key cryptography /

**Date: **received 25 Sep 2006

**Contact author: **ynawaz at engmail uwaterloo ca

**Available format(s): **PDF | BibTeX Citation

**Version: **20060926:095149 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]