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).

• Thanks, I guess you should exchange $z_0$ and $z_1$. How do you recover $r$ and $b$ from same $a$ in two executions? – Shuzheng Mar 2 '17 at 17:25
• $b$ should be a single bit. – Shuzheng Mar 2 '17 at 17:59
• Yes sorry I've exchanged the roles of $y$ and $g$ in my answer. If the same $a$ is used with challenges $0$ and $1$, then you will have $z_0 = r + u$ with the challenge $1$, and $u$ with the challenge $0$, and you recover $r$ by taking the difference between the two messages. Same thing for $z_1$. About $b$ being a single bit, you only asked for a proof that the prover knows how to open. This tells nothing on what $b$ is. If you want him to prove that he knows an opening such that the committed message is a bit, it can be done but requires a more complicated ZK proof. – Geoffroy Couteau Mar 2 '17 at 18:57
• Yes, sorry. I consider only but commitments. What fails is that the difference may not be a bit. Is it difficult to prove soundness for bit commitment? – Shuzheng Mar 2 '17 at 18:59
• Not difficult, but different and about twice more costly. Essentially, using proofs of same discrete log in different basis, you can prove knowledge of messages satisfying some multiplicative relation. In your case, you would prove that you know how to open $c$ and $yc^{-1}$ to plaintexts $(m,m')$ so that $m \cdot m'$ is zero. This is because if $c$ commits to $m$, $yc^{-1}$ commits to $1-m$, and $m(1-m) = 0$ is equivalent to saying that $m$ is a bit. But that's another question, and if you need a more detailed answer to see how to do that in practice, you should maybe ask a new question. – Geoffroy Couteau Mar 2 '17 at 19:15