To find nonlinear invariant of S box

Question

I read a paper about a nonlinear invariant attack that is Y.Todo et. al's "Nonlinear Invariant Attack: Practical Attack on Full SCREAM, iSCREAM, and Midori64"

In this paper's Appendix A., they said that

Then, by Gaussian elimination like computation, we compute matrix $M'=[M_1'\|M_2']. $ If rows of $M_2'$ are $[0,0,...,0]$ or $[1,0,0,...,0]$, the corresponding row of $M_1'$is the basis of $U(S)$

I wonder why that is the basis of $U(S)$.

In my thinking corresponding row of $M_1'$ such that the row of $M_2'$ are $[1,0,0,...,0]$ or $[0,1,0,0,...,0]$ or $...$ or $[0,0,0,...,0,1]$ is the basis of $U(S)$.

Can you show me why "If rows of $M_2'$ are $[0,0,...,0]$ or $[1,0,0,...,0]$, the corresponding row of $M_1'$ is the basis of $U(S)$" is right.

Answer 1

Keep this fact.

By linear algebra, we can know that $M'_{1} \times M=M'_{2}$.

Let $\beta _i$ be a row of $M'_{1}$ which is correspond to $M'_2$ 's $[0,\ldots,0]$ row

and let $\beta_i=[\beta_{0,i},\beta_{1,i},\ldots,\beta_{2^n-1,i}]$

Then we can know that $\beta_{i} \times M=[0,\ldots,0] $ by above fact.

So, if we define $b_i(x)=\beta_{0,i}x^0 \oplus \beta_{1,i}x^1 \oplus \cdot\cdot\cdot \oplus \beta_{2^n-1,i}x^{2^n-1}$.

Then,

\begin{align} b_i(x)\oplus b_i(S(x))= & \bigoplus_{u\in\mathbb{F}_2^n}\beta_{u,i}\big(x^u \oplus S(x)^u\big)\\ = & \bigoplus_{u\in\mathbb{F}_2^n} \beta_{u,i}\big(\bigoplus_{v\in\mathbb{F}_2^n} \lambda_{u,v}x^v \big)\\ = & \bigoplus_{u\in\mathbb{F}_2^n}\big(\bigoplus_{v\in\mathbb{F}_2^n}\beta_{u,i}\lambda_{u,v}\big)x^v\\ =& 0 \end{align}

We can apply this formula similarly to the case of $[1,0,\ldots,0]$.