2
$\begingroup$

Consider the Schnorr identification protocol. Let $x$ be secret key, $u$ be public key, $r(\xleftarrow{$} \mathbb{Z}_q )$ be a random number with $u_r=g^r$ the commitment that prover uses at first round, and $c(\xleftarrow{$} C)$ be the challenge that verifier challenges to the prover at second round. At the last round, the prover sends $s=r+cx$ to the verifier.

Here is my question: why is $s$ of the form $r+cx$? Why not $r+c+x, rc+x, rx+c, rxc$?

When $s=rx+c$ or $rxc$, it seems that the verifier can not verify by computing since $g^{rx+c}=u^r g^c = u_r^x g^c $ and $g^{rxc}=u_r^{xc}=u^{rc}$ but the verifier does not know $r$ and $x$. However, I don't understand why the others do not work.

$\endgroup$

1 Answer 1

4
$\begingroup$

As you correctly note, the responses $rx+c$ and $rxc$ cannot be efficiently verified (without access to a Diffie-Hellman solver).

The $r+c+x$ variant is a bad idea. Suppose as you say that Peggy has a secret value $x$ and commits to it with $u,u_r$. (Naughty) Victor sends the challenge $c$ and receives the response $s=r+c+x$ so that they can confirm $g^s=u\cdot g^c\cdot u_r$ all well and good?

Now (Naughty) Victor can claim to know $x$ and commit to it with $u,u_r$ even though he does not have knowledge of $x$. A victim Murphy can send a challenge $c'$ and Victor can respond with $s'=s-c+c'=r+c'+x$ which passes validation and Murphy believes that Victor knows $x$ even though he does not. Victor can cover his tracks better by replacing $u_r$ with $u_{r'}=u_r\cdot g^d$ and then instead using the response $s'=s-c+c'+d$.

The $rc+x$ variation is fine and the systems can be shown to give equivalent information. If $c$ is a challenge under the usual Schnorr protocol we can transform this into a challenge in your variant by setting $c'=c^{-1}\mod q$ and similarly transform the response $s'=c's$.

However it would not be good to have half the world using one variant of the protocol and the other half using the other and so it is best to fix on a single choice.

$\endgroup$
1
  • 2
    $\begingroup$ Thank you so much for your kind explanation. I understood everything clearly. Have a nice rest of the day! $\endgroup$
    – 이승우
    2 days ago

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.