# Cheon's discrete log attack, and its relevance to zk-SNARKs
The classic discrete log problem for a group $G$ of prime order $p$, is given $g,h\triangleq g^{\alpha}$, for uniformly chosen $g\in G, \alpha\in \mathbb{F}_p$, return $\alpha$.

Here is an interesting observation about DL we will use in a bit later. Suppose you had an algorithm $A$ for DL, for a group of order $p-1$, instead of $p$. Can you use it to solve DL for $G$?

The observation is *you can when $A$ only performs equality checks and multiplications of group elements*: Suppose this is the case; and suppose $\eta$ is a generator of $H\triangleq \mathbb{F}_p^*$.
Then we can run $A$ "in the exponent": Whenever $A$ wishes to multiply an element $\beta\in H$ by $c\in H$ we will *exponentiate* $g^\beta$ by $c$. Whenever $A$ wishes to compare $\beta,\gamma\in H$, we will compare $g^\beta$ and $g^\gamma$.

The result of running $A$ in the exponent like this, will be an element $c$, such that $\eta^c=\alpha$.
Since we know $\eta$ we've obtained the solution to our original DL problem in $G$!
Now the question is whether there are DL algorithms of this form? Indeed, Shanks's Baby-Step Giant-Step algorithm, and Pollard's Rho are of this form. They have complexity $O(\sqrt{|H|})$.
## Cheon's attack in the zk-SNARK setting

Pairing based zk-SNARKs rely on the hardness of computing DL in elliptic curve groups; and in fact, they rely on a stronger assumption with "auxiliary inputs". Here the adversary is given
in addition to $g^\alpha$ additional powers of $\alpha$ in the exponent; i.e. $g^{\alpha^2},\ldots, g^{\alpha^d}$ for some integer $d$, and is tasked again with finding $\alpha$.

Here's how [Cheon](http://www.math.snu.ac.kr/~jhcheon/publications/2010/StrongDH_JoC_Final2.pdf) leverages these auxiliary inputs. Suppose that $d$ divides $p-1$; then $\alpha^d$ is in the subgroup $H_1$ of $d$'th powers in $H$; we have $|H_1| = (p-1)/d$.
This means that given a generator $\eta_1:=\eta^{d}$ of $H_1$, we can run BSGS or Pollard's Rho in the exponent as described, and find in time $O(\sqrt{p/d})$ a $c$ such that $g^{\eta_1^c} = g^{\alpha^d}$.

Thus, we have found the DL of $\alpha^d$ in $H_1$, and need to proceed to actually find $\alpha$. We will reduce this to a DL problem in another subgroup of $H$ - the subgroup $H_2$ of $((p-1)/d)$'th powers. Since this subgroup has order $d$, the total complexity of Cheon's algorithm will end up being $O(\sqrt{p/d} + \sqrt{d})$. (In the zk-SNARK setting, $\sqrt{p/d}$ will be by far the dominant factor - see [Kobi's writeup](https://ethresear.ch/t/cheons-attack-and-its-effect-on-the-security-of-big-trusted-setups/6692)).

The reduction is as follows. We can write $\alpha = \eta ^ {k_0+k_1\cdot (p-1/d)}$, for $0\leq k_0 < (p-1)/d$ and $0\leq k_1< d$.
Then we have
$\alpha^d = \eta_1^ {k_0+k_1\cdot (p-1/d)}= \eta_1^{k_0}$;
so $k_0$ is just the $c$ we've already found, and it remains to find $k_1$ to determine $\alpha$.

Denote $\eta_2 \triangleq \eta^{(p-1)/d}$. Rearranging the equation we started with for representing $\alpha$, we have
$\eta_2 ^ {k_1} = \alpha\cdot \eta^{-k_0}$.
Denote $\alpha' \triangleq \alpha\cdot \eta^{-k_0}$. We can now find $k_1$ by solving the DL of $\alpha'$ w.r.t $\eta_2$ in $H_2$.

## References

[1] Cheon, Jung Hee. "Discrete logarithm problems with auxiliary inputs." Journal of Cryptology 23.3 (2010): 457-476.