3
$\begingroup$

When I am trying to learn deeper to Schnorr Protocol. I found that for deference there is more than one response and verify pair. But I am not sure am I right.

We will use Schnorr Protocol to prove the knowledge of $x$ in $y=g^x$. Here is the details of Schnorr Protocol, first prover send $t=g^r$ where $r$ is a random number to verifier. Verifier send challenge $c$ to prover, next step prover will calculate response and let verifier calculate is it correct by a function. Here is the question.

For $y=g^x$, $t=g^r$ and $c$, we have 3 equation below.

  1. $g^x g^{rc}=yt^c$ $\rightarrow$ $g^{x+rc}=yt^c$
  2. $g^{xc} g^r=y^ct$ $\rightarrow$ $g^{xc+r}=y^ct$
  3. $(g^x g^r)^c=y^ct^c$ $\rightarrow$ $g^{c(x+r)}=(yt)^c$

Can I say I can choose either one of that pair to finish the protocol?

  1. response $s=x+rc$, verify $g^s=yt^c$
  2. response $s=xc+r$, verify $g^s=y^ct$
  3. response $s=c(x+r)$, verify $g^s=(yt)^c$

Am I correct?

$\endgroup$

1 Answer 1

4
$\begingroup$
  1. response $s=c(x+r)$, verify $g^s=(yt)^c$

This one doesn't work; a lying prover can chose $t = y^{-1}g^n$, for an arbitrary $n$. Then, when the challenger responds with a $c$, the lying prover can respond with $s = nc$, satisfying the relationship.

The other two are good; the second is the standard Schnorr, and the first is standard Schnorr proof of the inverse relationship, that is, if you're proving the knowledge of $y^{x'} = g$ (which is equivalent to knowledge of $g^x = y$)

$\endgroup$
3
  • $\begingroup$ the only thing - the second option is the standard Schnorr, while the first one is a mirror $\endgroup$ Apr 12, 2020 at 20:26
  • $\begingroup$ Oops, you're right - I'll fix it... $\endgroup$
    – poncho
    Apr 12, 2020 at 20:27
  • $\begingroup$ btw I don't agree that the first option is just a simple direct mirror for the case of $y^x = g$, if I understand you correctly. I agree that the the security is equivalent. But - prover should check for $c=0$, in which case the key is immediately revealed! This is why the original Schnorr is a bit better $\endgroup$ Apr 12, 2020 at 20:43

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.