---
tags: security-proofs
---
# Collision Resistance of `compress` Function
**Disclaimer:** This documentation was written on May, 2022. It is intended to give readers a high-level understanding. The codebase is the canonical source of truth, and over time this document might fall behind the implementation details of the code.
###### tags: `audit`
##### Original Author: Arijit

Our `compress` function works as a keyed hash function $H_\rho(\mathbf{x})$ which takes a key $\rho$ and a vector $\mathbf{x}$ as input and outputs a scalar (x-coordinate of a curve point to be precise). The length of the input vector $n_{\rho}$ depends on the key $\rho$. For the same key, the generators used for hashing and the length of the input vector remain the same. They changes when the key is changed. We want to show that either for same key or for different key, collision is infeasible.

First, for a fixed key $\rho$, We want to show that it is infeasible for a PPT adversary to produce distinct $\mathbf{x}, \mathbf{x'}$ such that,
$$
H_{\rho}(\mathbf{x}) = H_{\rho}(\mathbf{x'}).
$$
In particular, $H_{\rho}(\mathbf{x})$ is the x-coordinate of point $A$, where
$$
A = (\gamma_1 P^{\text{aux}}_1+\lambda_1P_1-s_1P^{\text{skew}}_1) + (\gamma_2 P^{\text{aux}}_2+\lambda_2P_2-s_2P^{\text{skew}}_1) + \ldots + (\gamma_n P^{\text{aux}}_n+\lambda_nP_n-s_nP^{\text{skew}}_n).
$$
Here $(\gamma_i, \lambda_i)$ is the tuple of quad sum for the scalar $x_i, i \in [n]$ and $s_i$ is the corresponding boolean skew variable (we are denoting $n_{\rho} = n$ for simplicity). Similarly, $H_{\rho}(\mathbf{x'})$ is the x-coordinate of point $B$, where

$$
B = (\gamma'_1 P^{\text{aux}}_1+\lambda'_1P_1-s'_1P^{\text{skew}}_1) + (\gamma'_2 P^{\text{aux}}_2+\lambda'_2P_2-s'_2P^{\text{skew}}_1) + \ldots + (\gamma'_n P^{\text{aux}}_n+\lambda'_nP_n-s'_nP^{\text{skew}}_n).
$$
Both $A$ and $B$ satisfy the curve equation $y^2 = x^3 - 17$. For collision to occur, both of their x-coordinates are the same. This makes $y_1 = \pm y_2$. Then either of the following should happen,

$$
A+B = \mathcal{O} \text{ or } A=B.
$$
$A+B = \mathcal{O}$, implies

$$
\begin{aligned}
&(\lambda_1+\lambda'_1)P_1+(\lambda_2+\lambda'_2)P_2+\ldots+(\lambda_n+\lambda'_n)P_n+\\
&+(\gamma_1+\gamma'_1)P^{\text{aux}}_1+\ldots+(\gamma_n+\gamma'_n)P^{\text{aux}}_n \\
&-(s_1+s'_1)P^{\text{skew}}_1-\ldots-(s_n+s'_n)P^{\text{skew}}_n= \mathcal{O}.
\end{aligned}
$$
Here each $\lambda_i,\lambda'_i$ are strictly less than $\frac{p}{2}$, giving us non-zero (not zero vector) scalar solution (From the anlysis given [here](https://hackmd.io/gRsmqUGkSDOCI9O22qWXBA?view), we have $1 \le \lambda < 2^{251} < \frac{p}{2}$, $-15 \le \gamma \le 15$).

$A-B = \mathcal{O}$, implies

$$
\begin{aligned}
&(\lambda_1-\lambda'_1)P_1+(\lambda_2-\lambda'_2)P_2+\ldots+(\lambda_n-\lambda'_n)P_n+\\
&+(\gamma_1-\gamma'_1)P^{\text{aux}}_1+\ldots+(\gamma_n-\gamma'_n)P^{\text{aux}}_n \\
&+(s'_1-s_1)P^{\text{skew}}_1 +(s'_2-s_2)P^{\text{skew}}_2+\ldots+(s'_n-s_n)P^{\text{skew}}_n= \mathcal{O}.
\end{aligned}
$$
Here also we get non-zero scalar solution because we are assuming that collision has occurred.

Note that in both the cases, we do not need to constraint the values of $s$ variables since that will make the adversary more powerful.

Hence, to prove that `compress` function is collision resistant, we need to show that given a set of uniformly distributed generators $(G_1,G_2,\ldots,G_m) \in \mathbb{G}^m$, it is infeasible to find $(a_1,a_2,\ldots,a_m) \in \mathbb{F}_p^m$, such that
$$
\sum_i a_i G_i = \mathcal{O}.
$$
In particular, we want to show that $\text{VDL} \iff \text{DL}$ holds. Here the experiment VDL is defined as follows.
1. A PPT adversary $\mathcal{A}$ is given a set of uniform generators $G_1, G_2,\ldots,G_m$ and the underlying group $\mathbb{G}$.
2. It outputs a set of non-zero scalars $a_1,a_2,\ldots,a_m$.
3. $\mathcal{A}$ succeeds if,
$$
\sum_i a_i G_i = \mathcal{O},
\tag{i}
$$
holds. The VDL assumption states that for all PPT $\mathcal{A}$, there exists a negligible function $\mathsf{negl}(\lambda)$ which upperbounds the success probability of $\mathcal{A}$.

The experiment DL is defined below.
1. A PPT adversary $\mathcal{B}$ is given $(\mathbb{G},G,xG)$, where x is randomly sampled from $\mathbb{F}_p$.
2. $\mathcal{B}$ succeeds if it successfully outputs $x$.
The DL assumption states that for all PPT $\mathcal{B}$, there exists a negligible function $\mathsf{negl'}(\lambda)$ which upperbounds the success probability of $\mathcal{B}$.

In the following, we show that the both directions hold.
* To show that $\text{VDL} \implies \text{DL}$
We show this by showing if there exists a PPT DL adversary, then we can easily construct a PPT VDL adversary using it (breaking DL implies breaking VDL).
Suppose there exists a PPT DL adversary $\mathcal{B}$. Given $(\mathbb{G},G,Q=xG)$, it can outputs $x$. We construct a PPT VDL adversary $\mathcal{A}$ using $\mathcal{B}$ as a subroutine.
1. $\mathcal{A}$ is given $G_1, G_2,\ldots,G_m \in \mathbb{G}$. It needs to output scalars $a_1,a_2,\ldots,a_m$ such that Equation (i) holds. It uniformly samples $a_2,a_3,\ldots,a_m \leftarrow \mathbb{F}_p$.
2. From (i), we get
$$
a_1G_1 = -(a_2G_2+\ldots+a_mG_m) = Q' \text{ (say)}.
$$
$\mathcal{A}$ computes $Q'$ and sends $(\mathbb{G},G_1,Q')$ to $\mathcal{B}$.
3. $\mathcal{A}$ sets the output of $\mathcal{B}$ as $a_1$. It outputs $a_1,a_2,\ldots,a_m$.

* To show that $\text{DL} \implies \text{VDL}$
Suppose there exists a PPT VDL adversary $\mathcal{A}$. Given a set of uniform generators $G_1, G_2,\ldots,G_m \in \mathbb{G}$, it outputs a set of scalars $a_1,a_2,\ldots,a_m \in \mathbb{F}_p$ such that Equation (i) holds. We construct a PPT DL adversary $\mathcal{B}$ using $\mathcal{A}$ as a subroutine.
1. $\mathcal{B}$ is given $(\mathbb{G},G,xG=Q)$. It needs to output $x$. It uniformly samples $j^* \leftarrow [m]$.
2. Next, It uniformly samples $x_1,x_2,\ldots,x_{j^*-1},x_{j^*+1},x_m \leftarrow \mathbb{F}_p$. For $i \in [m]\setminus j^*$, it sets $G_i = x_iG$. It sets $G_{j^*} = Q$. It sends $G_1,G_2,\ldots,G_m$ to $\mathcal{A}$.
3. $\mathcal{A}$ outputs $a_1,a_2,\ldots,a_m$ such that Equation (i) holds. From (i), we have
$$
\begin{align}
a_{j^*}xG &= -(a_1x_1+a_2x_2+\ldots+a_{j^*-1}x_{j^*-1}+a_{j^*+1}x_{j^*+1}+\ldots+ a_mx_m)G \\
\implies x &= -a^{-1}_{j^*}(a_1x_1+a_2x_2+\ldots+a_{j^*-1}x_{j^*-1}+a_{j^*+1}x_{j^*+1}+\ldots+ a_mx_m). \tag{ii}
\end{align}
$$
Here the statement that $a_{j^*}$ is non-zero and its inverse exists satisfies with high probability owing to the fact that $j^*$ is chosen randomly.
$\mathcal{B}$ computes and outputs $x$ using Equation (ii).

Thus we have shown that for the same key, collision is infeasible.

Now lets consider the case for $\rho, \rho'$ such that $\rho \neq \rho'$. Say, a PPT adversary produces $\mathbf{x} \in \mathbb{F}_p^{n_{\rho}},\mathbf{x'} \in \mathbb{F}_p^{n_{\rho'}}$ such that $H_{\rho}(\mathbf{x}) = H_{\rho'}(\mathbf{x'})$.
In particular, $H_{\rho}(\mathbf{x})$ is the x-coordinate of point $A$, where
$$
A = (\gamma_1 P^{\text{aux}}_1+\lambda_1P_1-s_1P^{\text{skew}}_1) + (\gamma_2 P^{\text{aux}}_2+\lambda_2P_2 - s_2P^{\text{skew}}_2) + \ldots + (\gamma_{n_{\rho}} P^{\text{aux}}_{n_{\rho}}+\lambda_{n_{\rho}}P_{n_{\rho}}-s_{n_{\rho}}P^{\text{skew}}_{n_{\rho}}).
$$
Similarly, $H_{\rho'}(\mathbf{x'})$ is the x-coordinate of point $B$, where
$$
B = (\gamma'_1 R^{\text{aux}}_1+\lambda'_1R_1 -s'_1R^{\text{skew}}_1) + (\gamma'_2 R^{\text{aux}}_2+\lambda'_2P_2-s'_2R^{\text{skew}}_2) + \ldots + (\gamma'_{n_{\rho'}} R^{\text{aux}}_{n_{\rho'}}+\lambda'_{n_{\rho'}}R_{n_{\rho'}}-s'_{n_{\rho'}}R^{\text{skew}}_{n_{\rho'}}).
$$
Here all the generators are uniformly and independently generated. For collision to occur, either $A+B=\mathcal{O}$ or $A-B=\mathcal{O}$ has to satisfy. This implies the adversary has to come up with a non-zero scalar solution $(a_1,\ldots,a_{n_{\rho}+n_{\rho'}})$ such that,
$$
\sum a_iX_i = \mathcal{O},
$$
holds ($X_i$s are appropriate generators). However, this is infeasible owing to the VDL assumption (discussed above). $\blacksquare$