2
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Possible duplicate of Disjunction of several instances of sigma protocol $\endgroup$
    – Maeher
    Mar 4, 2019 at 6:42
  • $\begingroup$ The question you linked only describes the general approach. My question asks specifically how the protocol would work. $\endgroup$
    – Panos
    Mar 4, 2019 at 15:02
  • 3
    $\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, 2019 at 15:38

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.