1
$\begingroup$

In the Shnorr protocol where the prover wants to prove he has a witness $w$ for $g^w$ the following interactions happen:

  • the prover chooses a random $r$, calculates $y=g^r$ and sends $y$

  • the verifier sends a challenge $x$

  • the prover calculates $t=xw+r$ and sends it to the verifier

  • the verifier tests if $g^t=(g^w)^x.y$

My question is why the verifier sends a challenge. Would he be convinced if the prover just sends $t=r+x$ and the verifier tests if $g^t=g^w.y$? Plus $t$ won't reveal the witness.

$\endgroup$

1 Answer 1

3
$\begingroup$

my question is why the verifier sends a challenge, would he be convinced if the prover just sends $t=r+x$ and the verifier tests if $g^t=g^w \cdot y$ ?

That is, why doesn't the prover just send $t$ and $y$? Well, anyone can pick a random $t$ and compute $y = g^t \cdot (g^w)^{-1}$. Because $g^w$ is public, this can be computed by anyone, and so wouldn't serve as a proof of knowledge.

And, it is easy to find a solution to $g^t=(g^w)^x \cdot y$ (without knowing $w$), if you know the $x$ value before selecting the $y$ (and you suggested a constant $x=1$, hence the prover knows it up-front). However, if you can find a solution for $g^t=(g^w)^x \cdot y$ for two different $x$'s, that's different; it's easy to show that with solutions to two different $x$'s (and the same $y$), we can recover $w$ (and hence someone who can do that must know $w$). On the other hand, we can't just give out two solutions (as that means the verifier would then be able to deduce $x$).

So, what we do is get the prover to give a solution for an $x$ he cannot predict in advance; either he got extremely lucky (and he guessed the correct $x$ value when he generated $y$), or he does in fact know multiple solutions (and hence knows $w$).

$\endgroup$

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.