1
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.