Cryptography
schnorr-identification
Updated Sun, 04 Sep 2022 18:31:32 GMT

In Schnorr identification protocol, what happens if the prover uses r+c+x or rx+c.. etc. rather than r+cx?


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.




Solution

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.





Comments (1)

  • +2 – Thank you so much for your kind explanation. I understood everything clearly. Have a nice rest of the day! — Aug 05, 2022 at 11:36  


External Links

External links referenced by this document: