1
$\begingroup$

All zero-knowledge protocols I have read so far for discrete log works like this:

1) Prover generate a random number $r$, creates a commitment $t=g^r$ and sends $t$ to the verifier.

2) Verifier generates a random challenge $c$ and sends it to the prover.

3) Prover creates a response $s=r+x*c$ and sends it to the verifier

My question is: is the security affected in any way if, in step 3, the prover responds with $s=r+x+c$?

I don't understand why multiplication $x*c$ is used instead of sum $x+c$.

$\endgroup$
  • $\begingroup$ Have you actually tried to use $x+c$? What happens to your security proof then? $\endgroup$ – fkraiem Jun 25 at 7:20
  • $\begingroup$ $x=s-c$ but that's not the case when you use the random from step 1 $\endgroup$ – mip Jun 25 at 7:30
1
$\begingroup$

Hint: what happens if the prover, instead of sending $g^r$ for a random $r$ that he knows in the first round, sends instead $g^{-x}\cdot g^r$ for a random $r$ that he knows?

$\endgroup$
  • $\begingroup$ Any men-in-the-middle would be able to recover $g^{x}$ and reply to any subsequent challenges. $\endgroup$ – shumy Jun 27 at 14:57
  • $\begingroup$ This is not the issue here, $g^x$ is public. The point is to see how sending this first flow allows the prover to cheat, I.e., send a last flow that will ne accepted by the verifier, even without knowing $x$. $\endgroup$ – Geoffroy Couteau Jun 27 at 14:59
  • $\begingroup$ He didn't say it was public. Anyway, the result is the same. It can reply correctly without knowing $x$. I don't want to overlap your answer. $\endgroup$ – shumy Jun 27 at 15:06
  • 2
    $\begingroup$ Right, he did not say it, but it is - his question is based on the classical Schnorr protocol, where the goal is to prove knowledge of the discrete log $x$ of a public group element $g^x$ :) But if you saw why it is possible to successfully answer every challenge here, then you got the solution right. $\endgroup$ – Geoffroy Couteau Jun 27 at 15:09

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.