# On the Subspace Attack on Poseidon

## Notation

Let $t$ be the width. Let us the following notation for round $r\geq 0$:
* $A_r[]$ -- the ARC input words.
* $B_r[]$ -- the Sbox input words, i.e. the ARC outputs.
* $C_r[]$ -- the MixColumn input words, i.e. the Sbox outputs.

We thus have the following relations, assuming that only the S-box 0 is active in partial rounds:
* ARC: $A_r[i]+c_{r,i}=B_r[i]$;
* $\mathrm{SB}_r$: $(B_r[i])^5 = C_r[i]$ where $i=0$ for $R_F/2\leq r <R_P+R_F/2$ and $0\leq i <t$ for other $r$.
* $\mathrm{SB}_r$: $B_r[i] = C_r[i]$ where $i>0$ and $R_F/2\leq r <R_P+R_F/2$.
* MC: $A_{r+1}[] = M*C_r[]$.

Denote $\mathrm{Rd}_r= \mathrm{SB}_r\circ\mathrm{ARC}\circ \mathrm{MC}$

## Attack Idea

Consider the following set :
$$
S(k) = \{ \mathbf{x}\in \mathbb{F}^t\,|\,M^r\mathbf{x}=[0,*,*,\ldots,*],\,r\leq k\}.
$$

Suppose $y=a+x$ where $x\in S(k)$. Then
$$
\mathrm{MC}(y) = MC(a)+Mx= MC(a)+[0,*,*,\ldots,*]
$$
Adding the other operations we get
$$
\mathrm{ARC}(\mathrm{MC}(y)) = MC(a)+Mx+\mathbf{c}_r.
$$
And
$$
\mathrm{SB}(\mathrm{ARC}(\mathrm{MC}(y)) = \mathrm{SB}(MC(a)+\mathbf{c}_r)+Mx = \mathrm{SB}(\mathrm{ARC}(\mathrm{MC}(a))+Mx.
$$
Therefore
$$
\mathrm{Rd}_r(a+x) = \mathrm{Rd}_r(a) + Mx.
$$
Since $Mx\in S(k-1)$, we obtain that
$$
\mathrm{Rd}_{r+k}(\mathrm{Rd}_{r+k-1}(\cdots \mathrm{Rd}_{r+1}(a+x)\cdots)) = \mathrm{Rd}_{r+k}(\mathrm{Rd}_{r+k-1}(\cdots \mathrm{Rd}_{r+1}(a)\cdots)) +M^kx
$$
So, if denote $k$ rounds by $F_k$, we get that
$$
F_k(x+a) = F_k(a)+M^kx.
$$

## Property

We thus proved that if $\Delta y\in S(k)$
then
$$
F_k(y+\Delta y) = F_k(y)+L(\Delta y),
$$
where $L$ is an affine function

## System of Equations

Let us split the permutation into 3 transformations: first $F_{start}$, then $F_k$, then $F_{end}$.

The standard system of equations is the following:
$$
F_{start}(a)=b;\;F_k(b)=e,\;F_{end}(e)=f
$$
We can increase the number of solutions as follows:
$$
F_{start}(a)=b;\;F_k(c)=d,\;F_{end}(e)=f,\;c-b\in S(k),\;e-d=M^k(c-b)
$$
This gives $k+t$ extra linear equations and $2t$ extra variables $c,d$. We can express $(t+k)$ variables via $(t-k)$ ones linearly, thus having
* $t$ equations for $F_{start}$
* $t$ equations for $F_k$ degree $d^k$.
* $t$ equations for $F_{end}$.

We also have $(5t-k)$ variables and $2t-k$ degree of freedom.

### Option 1
We fix $c$ (=the coset of $S(k)$ we search the solutions in) thus eliminating $t$ equations and $2t$ variables. Eventually we get $3t-k$ variables and $2t$ equations of the same degree (=degree of $F_{start/end}$). We can the consider the preimage problem with eliminating $t-1$ output variables and equations, which leaves us with $t+1$ equations and $2t-k+1$ variables, of which we can fix $(t-k)$ ones.

As a result we have $(t+1)$ equations of $(t+1)$ variables. Each equation, assuming we position $F_{k=t-1}$ in the middle of the cipher, has degree $d^{R/2-t/2}$. Thus for the Grobner basis computation we have
$$
D_{reg} = 1 + (t+1)(d^{R/2-t/2}-1),
$$
and the GB computation complexity is at least
$$
\binom{(t+1)d^{R/2-t/2}}{t+1}^2 \approx (t+1)^{2t+2}d^{(R-t)(t+1)}
$$
For this to exceed $2^{128}$, we need
$$
(R-t)(t+1)\log_2 d+(2t+2)\log_2(t+1) \geq 128,
$$
or
$$
R \geq \frac{128}{(t+1)\log_2 d}-2\log_d(t+1) + t,
$$
which for $t>1$ is not better than the previous best known attack.

### Option 2
We keep a system with equations of different degree.