# 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\%.