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$
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$ – Mikhail Koipish Apr 12 '20 at 20:26
  • $\begingroup$ Oops, you're right - I'll fix it... $\endgroup$ – poncho Apr 12 '20 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$ – Mikhail Koipish Apr 12 '20 at 20:43

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.