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

1. Notation Group elements (curve points) are capitals $K,R,P,\ldots$ Scalars (field elements) are lowercase $s,k,\ldots$ Scalar multiplication in the group is $[k]P$. Vectors are bold: $\mathbf{D}$. Tuples: $\mathcal{C}$ 2. Components 2.1 Cryptographic Primitives Curve $\mathbf{E}$ defined over field $\mathbb{F}_q$ (supposedly BN254) with group of prime order $\mathbb{F}_r$;

5/26/20231. Problem $f\in \mathbb{F}^d[X]$; $(a_1,a_2,\ldots,a_d)\in \mathbb{F}$ $(c_1,c_2,\ldots,c_d)\in \mathbb{F}$ $c(X)$ such that $c(\omega^i) = a_i$ and $c(\omega^{d + i}) = c_i$ Prove that $f( c(w^i))=c_i$ for all $1 \leq i \leq d$. 2. Warmup: Proof of Division

11/20/2022Dmitry Khovratovich Problem: whenever we implement an algorithm that works over $Z_{N}$, with $N=2^{16}$ or $N=2^{32}$, we need to reduce all computations modulo $N$ and range-check all variables against $N$. These operations are expensive. We suggest a new scheme that implements the mod-$N$ arithmetic without range checks. 1. State of the art: Simplified Plonk Notation: $N =2^n$. First recall (and simplify) how Plonk arranges its witness.

11/18/20221. Notation $n$ -- ring degree (512 or 1024) $q$ -- modulus $=12289 = 3\cdot 2^{12}+1$ $\widehat{\beta} = \lfloor\beta^2\rfloor$ -- max norm (34 034 726 or 70 265 242) $\phi=X^n+1$ 2. Single Signature Verification Inputs:

9/7/2022
Published on ** HackMD**