Cryptography
zero-knowledge-proofs commitments
Updated Tue, 16 Aug 2022 17:19:40 GMT

Intuition Behind Commitment-Challenge-Response a.k.a. Sigma Protocols


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!




Solution

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.





Comments (5)

  • +0 – 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. — Apr 16, 2021 at 07:56  
  • +1 – 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. — Apr 16, 2021 at 09:07  
  • +0 – 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? — Apr 16, 2021 at 13:04  
  • +0 – Is this about avoiding a replay attack, where the prover just resends $r$ and $z$ without knowing $x$ to seemingly prove he knows $x$? — Apr 16, 2021 at 13:11  
  • +0 – 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. — Apr 16, 2021 at 14:30