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$
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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.