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.