Question about a proof-of-knowledge for discrete log

137 Views Asked by At

I'm reading a paper about proofs of knowledge for the discrete log problem and I'm having trouble understanding this bit (I'll condense the example to the relevant bits) :

We want to prove we know $x$ such that $y = g^x$ in some finite multiplicative group of order $q$ (prime). The prover first computes (where $v$ is random and $H$ is a hash) \begin{align*} t&=g^v \\ c&=H(g,y,t) \\ r&= v-cx \mod q \end{align*} The pair $(c,r)$ is then made public and the proof is verified by checking that $c=H(g,y,t')$, where $t'=g^ry^c$.

If a cheater was able to give a "proof", then they would have to fix $t'$ without knowledge of $c$, because the hash is hard to invert. It also seems necessary that when fixing the value $t'$ the prover was prepared to compute a proof for many other possible challenges. But this means that the cheating prover could also compute different representations of $t'$ to the bases $g$ and $y$, which implies a solution to the discrete log problem, and therefore knowledge of $x$

The bolded part is what's giving me problems. I'm not sure what's meant by "different representations of $t'$. Can someone help me understand this?

1

There are 1 best solutions below

0
On BEST ANSWER

Note that $t' = g^r y^c = g^{v-cx} (g^x)^c = g^v$. The paper is referring to the fact that there are many possible choices of $c$ and $r$ such that $g^v = g^r y^c$. Each different way of writing $t' = g^v = g^r y^c = g^{r'} y^{c'}$ is a "different representation" of $t'$. This like like saying that $1 \times 12 = 3 \times 4 = 6 \times 2$ are three different representations of $12$.

Edit: no idea why you are being downvoted. This is question is not at all off topic.