# NIZK proof for randomization of DLOG

One can have a NIZK proof for DLOG by applying Fiat-Shamir heuristic to Sigma protocol, such that one can prove non-interactively that $$x$$ is discrete logarithm of $$X = g^x$$. Then, in simulation based proofs, the simulator can extract the witness $$x$$.

What interest me is whether a party $$P_2$$ given $$X = g^x$$ and DLOG proof $$\pi \gets (\{ \exists x' \mid X = g^{x'} \}, x)$$ from a party $$P_1$$, can give another proof for the randomization of $$X$$. More precisely, $$P_2$$ samples a random $$r$$, calculates $$X' = X^r$$, and then gives a proof like $$\pi' \gets (\{ \exists r' \mid X' = X^{r'} \}, r)$$ or any other proof, such that the simulator simulating $$P_1$$ can later extract the randomized witness $$x \cdot r$$ either from the proof $$\pi'$$ received from $$P_2$$ or from the combination of both proofs $$\pi$$ and $$\pi'$$?

Please note that when I talk about proofs here I mean always non-interactive version.

NOTE: I know that Sigma protocol cannot be re-rerandomized. But, is there any other type of proof that will let you to prove this re-rerandomization and extract the witness?

## 2 Answers

Yes $$P_2$$ can generate $$\pi' \gets (\{ \exists r' \mid X' = X^{r'} \}, r)$$, which proves that he knows $$r$$ that is the Dlog of $$X'$$. Since $$r$$ is chosen by him and $$X$$ is public, he can do this just as any normal DLOG proofs.

However, $$P_2$$ cannot generate $$\pi'' \gets (\{ \exists xr' \mid X' = g^{xr'} \}, xr)$$, which I guess is what you actually want. This would require $$P_2$$ to know $$xr$$, instead of just $$r$$.

No. Since in the 3rd phase of Sigma protocol, i.e. the response phase, the response $$s$$ is $$t + hash(T).x$$. Here $$X = g^x$$ and $$T = g^t$$.
Changing the response such that it looks like $$t + hash(T).x.r$$ is not possible as $$P2$$ does not know $$t$$. Multiplying $$s$$ by $$r$$ will change it to $$t.r + hash(T).x.r$$