On the number of linearly independent quadratic equations for S-boxes based on power mappings

Abstract

One of the important factors that determines the security of an S-box on the point of view of algebraic attacks is the number of linearly independent multivariate quadratic equations on $\mathbb{F}_2$ it satisfies. Many previous researches analyzed the equations on $\mathbb{F}_2$ of S-boxes based on power functions, as they can be used to build an S-box of an arbitrary size. Courtois et al.\ proved the number of equations for an inverse S-box of arbitrary size, and expanding upon that, Nawaz et al.\ presented an algorithm to count the number of equations for an S-box based on an arbitrary power function.

In this paper, we extend the previous results to apply to $\mathbb{F}_{2^m}(m \ne 1, m|n)$, a subfield of $\mathbb{F}_{2^n}$. We first present an algorithm to count the number of quadratic equations of an S-box on the subfield. Next, we give proof that for one of the most frequently used S-boxes, the inverse S-box set on $\mathbb{F}_{2^n}$, the number of linearly independent quadratic equations on $\mathbb{F}_{2^m}$ is given as $n/m-1$. We expect to be able to apply the principles of algebraic attacks and analysis on subfields to new types of attacks which has not been researched before.