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

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

1 Answer 1

Reset to default
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?

Improve this answer
$\endgroup$
4
  • $\begingroup$ Any men-in-the-middle would be able to recover $g^{x}$ and reply to any subsequent challenges. $\endgroup$
    – shumy
    Commented Jun 27, 2019 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
    Commented Jun 27, 2019 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
    Commented Jun 27, 2019 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
    Commented Jun 27, 2019 at 15:09

Your Answer

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

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