2
$\begingroup$

In How To Prove Yourself: Practical Solutions to Identification and Signature Problems, Fiat and Shamir introduce a zero-knowledge identification scheme where

  1. The prover sends a commitment to the verifier
  2. The verifier sends a challenge to the prover (in shape of random coin tosses)
  3. The prover sends a response to the verifier
  4. The verifier checks if the response is correct

This is zero-knowledge and a Sigma protocol as described by Cramer in his PhD thesis.

My only experience with commitments is in fairly flipping a coin over telephone, in which case a commitment seems perfectly reasonable. But what is the basic intuition behind the commitment in the Fiat-Shamir case? Challenge and response are obviously part of the protocol, but why is the commitment needed? As far as I can tell, the commitment is not even revealed to the verifier in the Fiat-Shamir identification scheme!

Improve this question
$\endgroup$
1
  • $\begingroup$ Just intuitively and at a very high level: commitments are needed so that the prover does not change her mind when responding to the challenge. Typically, if you allow the prover to do this, then she will always be able to craft a response to the given challenge that passes whatever test the verifier runs. $\endgroup$ – Daniel Apr 15 at 21:27
1
$\begingroup$

As a concert example lets consider the protocol for knowledge of discrete-logarithm.

The aim of the protocol: P wants to prove that it knows $x$ for $pk=g^x$.

  1. commitment: P chooses a random $r$ and commit to it by sending $R=g^r$ to the verifier.

  2. challenge: the verifier chooses a random value $c$ and sends it to P.

  3. P sends $z=r+cx$ to the verifer.

  4. verification: the verifier checks if $g^z=R.pk^c$ if yes it accepts it.

Now what will happen if the prover does not commit to $R$ before sending $z$ ?

After receiving $c$ from the verifier, P chooses a random $z$ and finds $R'$ from the equation $g^z=R'pk^c$, i.e., it sets $R'=g^zpk ^{-c}$. Then it sends $R',z$ to the verifier. By this $R'$ it can pass the verification check, and the point is that it even does not use $x$ in $z$. This means a malicious prover who does not have $x$ can prove the knowledge of $x$! Putting together, commitment is necessary to protect the proof system against prover such that just the honest provers can convince the verifier.

Improve this answer
$\endgroup$
5
  • $\begingroup$ So $r$ serves to obfuscate $cx$? If $cx$ were just sent, no commitment used, the verifier could simply divide by $c$, which it knows, to retrieve $x$, right? Obfuscate in the sense that it renders retrieving $x$ by the verifier computationally infeasible. $\endgroup$ – cadaniluk Apr 16 at 7:56
  • 1
    $\begingroup$ It is true, anyway we need a random $r$ to hide $cx$, but the point is that the prover should commit to it at the beginning. otherwise it can choose a random $r'$ depending on the challenge while it even does not have any x to hide! it is just to mimic the protocol and convince the verifier that I am doing my job! This was an example to show why commitment is important. $\endgroup$ – A.Soleimani Apr 16 at 9:07
  • $\begingroup$ OK, that answers my question, thanks. But now I wonder why we need the challenge at all. Why not commit to $r$ by sending $R = g^r$ to the verifier and then sending $z = r + x$? If the prover knows $x$, then the verifier accepts after verifiying $g^z = Rpk$ (fulfilling completeness), if the prover does not know $x$, then finding the correct $z$ reduces to efficiently solving the discrete logarithm problem, right? So the challenge is not needed at all, or is it? $\endgroup$ – cadaniluk Apr 16 at 13:04
  • $\begingroup$ Is this about avoiding a replay attack, where the prover just resends $r$ and $z$ without knowing $x$ to seemingly prove he knows $x$? $\endgroup$ – cadaniluk Apr 16 at 13:11
  • $\begingroup$ Imagine there is no challenge, then before sending any thing else (even before sending the commitment), the prover applies the previous attack, i.e., it chooses a random $z$ and then finds $R$ from equation $g^z=R.pk$. Then it sends this $R$ as its commitment. Thus, the order is very important, commit, challenge, response. $\endgroup$ – A.Soleimani Apr 16 at 14:30

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.