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.

  • 1
    $\begingroup$ 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 $\endgroup$
    – asante
    Dec 21 '18 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}$.


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

  • 1
    $\begingroup$ could you explain more, not clear from here. $\endgroup$
    – kelalaka
    Dec 31 '18 at 20:37
  • $\begingroup$ @kelalaka I edit my answer. $\endgroup$
    – jyj
    Jan 2 '19 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.