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.
대수적 공격의 관점에서, S-box의 안전성을 결정하는 중요한 요소 중 하나는 해당 S-box로부터 유도되는 $\mathbb{F}_2$ 상에서의 다변수 이차 방정식의 수이다. 이전의 연구들은 임의의 크기의 S-box를 만들기에 용이한 지수 함수 꼴로 주어지는 S-box의 $\mathbb{F}_2$ 상에서의 방정식의 수에 대하여 연구하였다. Courtois et al.은 임의의 크기의 역원 함수에 기반한 S-box가 가지는 이차 방정식의 수를 증명하였으며, Nawaz et al.은 이 아이디어를 확장하여 임의의 지수함수 꼴의 S-box가 가지는 이차 방정식의 수를 세는 알고리즘을 제안하였다.
본 논문에서는 기존 연구 결과를 $\mathbb{F}_{2^n}$의 부분체인 $\mathbb{F}_{2^m}(m \ne 1, m|n)$에서 사용할 수 있도록 확장한다. 먼저 S-box가 부분체 위에서 가지는 이차 방정식을 세는 알고리즘을 제안한다. 다음으로 가장 자주 사용되는 S-box들 중 하나인 역원 함수에 기반한 S-box의 경우, $\mathbb{F}_{2^n}$ 상에서 정의된 S-box가 가지는 $\mathbb{F}_{2^m}$ 상에서의 선형 독립 이차 방정식의 수가 $n/m-1$임을 증명한다. 이를 확장함으로서 대수적 공격과 분석을 이전에는 연구된 바 없는 부분체 위에서 수행할 수 있게 되며, 이를 이용하여 새로운 종류의 공격을 수행할 수 있을 것으로 기대한다.
