# To find nonlinear invariant of S box

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.

• this is not in the direction of answering your question, but maybe helpful for you, too. There is a SageMath patch under review (that is, not yet included in SageMath), which implements an algorithm to compute nonlinear invariants for S-boxes: trac.sagemath.org/ticket/21252 Commented Dec 21, 2018 at 6:28

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]$$.

• could you explain more, not clear from here. Commented Dec 31, 2018 at 20:37
• @kelalaka I edit my answer.
– jyj
Commented Jan 2, 2019 at 1:43