Disjunctive zero knowledge proof of equality of committed values

Question

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.

Answer 1

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.