# Cycle Correlation Assumption

The adversary is given $\vec{G} \in \mathbb{G}_1^\ell, \vec{H} \in \mathbb{G}_2^\ell$ and challenged to find $\vec{a}, \vec{b}$ st.

$$
A = \langle \vec{a}, \vec{G} \rangle
$$

$$
B = \langle \vec{b}, \vec{H} \rangle
$$

And: $A = \sum_{i} b_i \in \mathbb{G}_1$ and $B = \sum_{i} a_i \in \mathbb{G}_2$.

Note that points are used both as scalars and group elements.

The assumption is that the adversary succeeds in producing such $\vec{a}, \vec{b}$ with only negl. probability.

## Reduction In The GGM

The assumption holds in the GGM since the encoding of points is random bit-strings (scalars):

# Cycle Collision Assumption

Adversary picks $R$, $\vec{a^{(1)}}$, $\vec{b^{(1)}}$, $\vec{a^{(2)}}$, $\vec{b^{(2)}}$ and wins if:

$$
A^{(1)} = R + \langle \vec{a^{(1)}}, \vec{G} \rangle, \ \
B^{(1)} = \langle \vec{b^{(1)}}, \vec{H} \rangle
$$

$$
A^{(2)} = R + \langle \vec{a^{(2)}}, \vec{G} \rangle, \ \
B^{(2)} = \langle \vec{b^{(2)}}, \vec{H} \rangle
$$

With:

1. $A^{(1)} = R + \sum_{i} b^{(1)}_i \in \mathbb{G}_1$ and $B^{(1)} = \sum_{i} a^{(1)}_i \in \mathbb{G}_2$ (a valid cycle with offset).
1. $A^{(2)} = R + \sum_{i} b^{(2)}_i \in \mathbb{G}_1$ and $B^{(2)} = \sum_{i} a^{(2)}_i \in \mathbb{G}_2$ (a valid cycle with offset).
3. $(\vec{a^{(1)}}, \vec{b^{(1)}}) \neq (\vec{a^{(2)}}, \vec{b^{(2)}})$ (no trivial solution)

## Reduction In The GGM