# Observation on Rescue

## One round of Rescue

Rescue has state $S = (S[1],S[2],
\ldots,S[w])$. Let round $r$ transform $S^r$ to $S^{r+1}$. The state undergoes the following transformation:
1. Root S-box application:
$$
T^r[i] \leftarrow (S^r[i])^{1/d},
\;1\leq i \leq w.
$$
2. MDS application
$$
U^r \leftarrow M\cdot T^r = \begin{bmatrix}m_{11} & m_{12} & ... & m_{1w}\\
...&...&...&...\\
m_{w1}&m_{w2}&...&m_{ww}\end{bmatrix}T^r.
$$
3. Constant addition
$$
V^r[i] \leftarrow U^r[i] + K^{2r}[i]
\;1\leq i \leq w.
$$
4. S-box application
$$
W^r[i] \leftarrow (V^r[i])^{d},
\;1\leq i \leq w.
$$
5. MDS application
$$
X^r \leftarrow M\cdot W^r.
$$
6. Constant addition
$$
S^{r+1}[i] \leftarrow X[i] + K^{2r+1}[i].
$$

## Equations for a single round

The Rescue designers assume that the following $2w$ equations describe a single round of Rescue and determine the degree of regularity:
1. Expressing $S^r$:
$$
S^r[i] = \left(\sum_j m_{ij}'U^r[j]\right)^d
$$
where $m_{ij}'$ are elements of the inverse matrix to $M$:
$$
M^{-1} = \begin{bmatrix}m_{11}' & m_{12}' & ... & m_{1w}'\\
...&...&...&...\\
m_{w1}'&m_{w2}'&...&m_{ww}'\end{bmatrix}
$$
2. Expressing $S^{r+1}$:
$$
S^{r+1}[i] = K^{2r+1}[i] +
\sum_j m_{ij}(U^r[j]+K^{2r}[j])^d
$$

## Our observation

For $d=3$ and $w=2$ we have 4 equations of degree 3. However, the degree-3 monomials have only $U^r[1],U^r[2]$ as variables, so there are only 4 of them. Therefore, we can construct a degree 2 equation that links together $S^r,S^{r+1},U$:
$$
\langle a_1,S^r\rangle + \langle a_2,S^{r+1}\rangle =
\langle (a_{31},a_{32},a_{33},a_{34},a_{35}),U^r[1],U^r[2],U^r[1]U^r[2],(U^r[1])^2,(U^r[2])^2\rangle +c,
$$
where $a_1,a_2$ are vectors and $a_{31},a_{32},a_{33},a_{34},a_{35},c$ are constants.

Thus we can replace one equation of degree 3 with another equation of degree 2, thus lowering the degree of regularity by 12.5\%.