Sigma protocol to prove that the prover knows how open a commitment Sigma protocol to prove that the prover knows how open a commitment. 


Consider the unconditionally hiding commitment scheme based on discrete log, i.e., the public key $p_k = (p,g,y)$, where $\langle g \rangle = Z_p^*$ is a generator and $y \in Z_p^*$.

To commit to a bit $b$, we proceed as follows: $c = \text{commit}(r,b)_{p_k} = y^bg^r \bmod p$. 

Now, I want to design a $\Sigma$-protocol to prove that the prover knows how to open $c$, where the challenge should be a single bit $e$.

Here the witness $w=(b,r)$ is input only to $P$, while $x = (p,g,y,z)$ is input to both $V$ and $P$.

Recall that conversations in a $\Sigma$-protocol are $(a,e,z)$.

My initial attempt is to make $P$ send a random commitment as $a$, and then ,depending on whether $e=0$ (or $e=1$), send some $z$ back to $V$.

However, I've trouble determining the $z$ and prove soundness.
Let $a \gets y^{u}g^{v}$, where $(u,v)$ are uniformly random exponents. $P$ sends a in the first flow, then receives a bit $e$ from $V$.

If $e = 0$, $P$ reveals $(u,v)$ and $V$ checks that $a$ is indeed $y^{u}g^{v}$ (hence that $P$ knows how to open $a$). If $e = 1$, $P$ reveals $z_0 = r + u \bmod q$ and $z_1 = b + v \bmod q$ ($q$ being the order of the group generated by $g$), and the verifier checks that $a\cdot c = y^{z_0}g^{z_1}$.

The intuition is the following: when $e=0$, $P$ proves that he can open $a$, and when $e=1$, he proves that he can open $a\cdot c$. As $P$ cannot anticipate the $e$ in advance, if this step is repeated many times, then $V$ is convinced that $P$ knows how to open $c$ with overwhelming probability. In other words, the protocol has soundness $1/2$.

To prove the soundness, you have to exhibit an extractor, id est, a simulator that will play the role of $V$, interacting with $P$, and that can extract $(r,b)$ from this interaction. This is what it means to "know" something: it can be learned from you. Of course, this simulator cannot just play as an honest verifier, because an honest verifier cannot learn the witness. The common method is to use rewinding: the simulator can run the prover, and rewind it to some intermediate step. By doing so, the simulator will ensure that the same first flow $a$ is the same in, say, two different executions, one with challenge $0$ and one with challenge $1$. From then it's easy to recover $r$ and $b$.

Things get slightly more complicated when you interact with a prover that succeeds with some noticeable probability $\varepsilon$, and not "always", but the same ideas work right, you just have to figure out the probability that $P$ succeeds twice in two runs of the protocol that are not really independent (as they share the same $a$); you can get the probability from standard probability lemmas (see the splitting lemma, for example).