I have read on ZK proof of equality of committed values, that is for $g^xh^y$ and $g^{x'}h^{y'}$, prove in ZK that $x = x'$ (can also be generalized if generators are different using sigma-protocols).

However I want to do a disjunctive (OR) proof as follows: For $g^{x_1}h^{y_1}$ and $g^{x_{1}'}h^{y_{1}'}$ and $g^{x_2}h^{y_2}$ and $g^{x_{2}'}h^{y_{2}'}$ prove in ZK that either $x_{1} = x_{1}'$ or $x_{2} = x_{2}'$. Any suggestions or ideas?

Upd: As suggested, I should highlight the fact that the generators are the same.

  • 2
    $\begingroup$ Possible duplicate of Disjunction of several instances of sigma protocol $\endgroup$ – Maeher Mar 4 '19 at 6:42
  • $\begingroup$ The question you linked only describes the general approach. My question asks specifically how the protocol would work. $\endgroup$ – bomberb17 Mar 4 '19 at 15:02
  • 2
    $\begingroup$ Well, take the sigma protocol you have, apply the Cramer, Damgaard, Schoenmakers construction and then you have the protocol for the disjuction. $\endgroup$ – Maeher Mar 4 '19 at 15:38

What's special about your question is the "global" use of generators $g,h$ for all the commitments. This allows for a nice shortcut, leading to some potential savings.

Asking for a proof that $x=x'$ for given $C=g^x h^y$ and $C'=g^{x'} h^{y'}$ only makes sense if we actually demand a proof of knowledge of all four exponents as well. Now, the interesting thing is that if some party already proved knowledge of the four exponents, it suffices to prove knowledge of $z=\log_h (C/C')$ to establish that $x=x'$. This latter proof can be done using the Schnorr protocol.

The basic assumption for Pedersen commitments is that nobody knows $\log_g h$, otherwise one cannot even speak about the exponents for a given commitment. So, given all these proofs it follows that we can write $C=g^x h^y=C' h^z=g^{x'} h^{y'+z}$, hence that $x=x'$ must hold (and $y=y'+z$).

The proof that you are asking for then boils down to the OR-composition of two Schnorr proofs, which is pretty efficient. This idea can be applied more generally, and was in fact the basis for an efficient construction of list signatures (see Lemma~1 in List Signature Schemes).

If knowledge of the four exponents has not been proved yet, it is more efficient to prove everything in one go using EQ-composition combined with OR-composition. Assuming that $x_1=x'_1$, we use an EQ-proof for $C_1,C'_1$ and a simulation of an EQ-proof for $C_2,C'_2$. This yields the following $\Sigma$-protocol:

  1. Prover sends announcement $(a_1,a'_1,a_2,a'_2)\leftarrow(g^{u_1} h^{v_1}, g^{u_1} h^{v'_1}, g^{r_2} h^{s_2} C_2^{-c_2}, g^{r_2} h^{s'_2} C_2'^{-c_2})$ with $u_1,v_1,v'_1,c_2,r_2,s_2,s'_2\in_R\mathbb{Z}_n$.

  2. Verifier sends challenge $c\in_R\mathbb{Z}_n$.

  3. Prover sets $c_1\leftarrow_n c-c_2$ and $(r_1,s_1,s'_1)\leftarrow_n (u_1+c_1\,x_1, v_1+c_1\,y_1,v'_1+c_1\,y'_1)$, and sends response $(c_1,r_1,s_1,s'_1,r_2,s_2,s'_2)$. Verifier sets $c_2 \leftarrow_n c - c_1$ and accepts if all of $g^{r_1} h^{s_1} = a_1 C_1^{c_1}$, $g^{r_1} h^{s'_1} = a'_1 C_1'^{c_1}$, $g^{r_2} h^{s_2} = a_2 C_2^{c_2}$, and $g^{r_2} h^{s'_2} = a'_2 C_2'^{c_2}$ hold.

| improve this answer | |

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.