Sigma protocol for AND-composition involving the same secret

Question

Say we have two public cyclic groups $G_1$, $G_2$ of corresponding prime orders $p_1$, $p_2$, and known generators $g_1$, $g_2$. Say $g_3$ is also a generator of $G_2$.
For publicly known $C_1$ and $C_2$, and secret $r$ and $m$, I want to prove:
$POK\{(r, m): C_1 = g_1^r \land C_2 = g_2^rg_3^m\}$
Note here that $C_2$ is a Pedersen commitment using the same $r$. How can I prove this statmement?

I know proving Discrete-Log is easy using Schnorr's identification protocol [1], proving knowledge of both factors in Pedersen commitment is also possible using Sigma protocols [2], and using a common challenge we can build AND-composition [3]. The challenge here is to prove for the same $r$.

Bonus: how can I prove it in zero-knowledge (instead of with honest-verifier-zero-knowledge)?

[1] https://pdfs.semanticscholar.org/8d69/c06d48b618a090dd19185aea7a13def894a5.pdf
[2] https://courses.cs.ut.ee/MTAT.07.003/2017_fall/uploads/Main/0907-sigma-protocol-for-pedersen-commitment.pdf
[3] https://www.math.leidenuniv.nl/~edix/oww/mathofcrypt/schoenmakers/sigma-Leiden2003.pdf

Answer 1

Proving this statement for groups $G_1, G_2$ of different order is a bit tricky. If the groups are of the same order, one can simply use EQ-composition (see [4], which are the lecture notes corresponding to reference [3] above).

For groups of different prime orders $p_1, p_2$, a simple $\Sigma$-protocol runs as follows. Let $n=p_1 p_2$.

1. Prover sends announcement $(a_1,a_2)$, where $a_1=g_1^u$ and $a_2=g_2^u g_3^v$ with $u\in_R\mathbb{Z}_n$ and $v\in_R\mathbb{Z}_{p_2}$.

2. Verifier sends challenge $c\in_R\mathbb{Z}_{\min(p_1,p_2)}$.

3. Prover sends response $(r_1,r_2)$, where $r_1=u+c\,r \bmod n$ and $r_2=v+c\,m \bmod p_2$. Verifier accepts if $g_1^{r_1} = a_1 C_1^c$ and $g_2^{r_1} g_3^{r_2} = a_2 C_2^c$.

To show special soundness, consider accepting conversations $(a_1,a_2;c;r_1,r_2)$ and $(a_1,a_2;c';r'_1,r'_2)$ that share the same announcement $(a_1,a_2)$, but have distinct challenges $c\neq c'$. Hence, we have: $$g_1^{r_1} = a_1 C_1^c,\quad g_2^{r_1} g_3^{r_2} = a_2 C_2^c,\qquad g_1^{r'_1} = a_1 C_1^{c'},\quad g_2^{r'_1} g_3^{r'_2} = a_2 C_2^{c'}.$$ Dividing these onto each other leads to: $$C_1 = g_1^{\frac{r_1-r'_1}{c-c'}}, \qquad C_2 = g_2^{\frac{r_1-r'_1}{c-c'}} g_3^{\frac{r_2-r'_2}{c-c'}}.$$ The witness is extracted by setting $r=(r_1-r'_1)/(c-c')\bmod n$ and $m=(r_2-r'_2)/(c-c')\bmod p_2$.

Note that the statement has to be interpreted with care: the values of $r\bmod p_1$ and $r\bmod p_2$ will in general not be equal, so the actual numbers appearing in the exponents of $g_1$ and $g_2$ may be very different from each other!

[4] https://www.win.tue.nl/~berry/CryptographicProtocols/LectureNotes.pdf

Answer 2

Let's change the formula to $C_1C_2=(g_1g_2)^{r}g_3^m$ and $C_2C_1^{-1}=(g_2g_1^{-1})^{r}g_3^m$. The prover just needs to prove that she knows how to open the two commitments as well as the random and the commited value are equal in two commitments, which is EQ form of [2] as you provided. Here is the protocol:

• The prover sends $a_1=(g_1g_2)^{u_1}g_3^{u_2}$ and $a_2=(g_2g_1^{-1})^{u_1}g_3^{u_2}$ for random $u_1$, $u_2$.
• The verifier sends a challenge $c$.
• The prover answers $d_1=u_1+c \cdot r$ mod $n$, $d_2=u_2+c \cdot m$ mod $n$ to the verifier.
• The verifier checks if $a_1(C_1C_2)^c = (g_1g_2)^{d_1}g_3^{d_2}$ and $a_2(C_2C_1^{-1})^c = (g_2g_1^{-1})^{d_1}g_3^{d_2}$

Completeness follows immediately.

special soundness: Given two accepting conversations $(a_1, a_2; c; d_1, d_2)$ and $(a_1, a_2; c'; d_1', d_2')$ with $c \neq c'$, we have $r = (d_1-d_1')/(c-c')$ and $m = (d_2-d_2')/(c-c')$

honest-verier zero-knowledge: chooses random $c, d_1, d_2$, setting $a_1=(g_1g_2)^{d_1}g_3^{d_2}(C_1C_2)^{-c}$ and $a_2=(g_2g_1^{-1})^{d_1}g_3^{d_2}(C_2C_1^{-1})^{-c}$ to simulate the conversation.

To Σ-protocol zero knoweledge, please refers to session 6.5 Zero-Knowledge from Σ-Protocols in Efficient Secure Two-Party Protocols for detailed information.

Most importantly, we need to argue the above protocol is equivalent to what you need. Generally suppose $C_1=g_1^{x_1}g_2^{x_2}g_3^{x_3}g'^{x'}$ and $C_2=g_1^{x_1'}g_2^{x_2'}g_3^{x_3'}g''^{x''}$, then you can check $C_1C_2=(g_1g_2)^{r}g_3^m$ and $C_2C_1^{-1}=(g_2g_1^{-1})^{r}g_3^m$ imply $x_1=r$, $x_1'=0$, $x_2=0$, $x_2'=r$,$x_3=0$, $x_3'=m$, $g'^{x'}=g''^{x''}=1$.

========================================================================

Let me correct my answer. The above protocol is for group $G_1=G_2$, for $G_1 \neq G_2$, we can process using following intuition:

It is known that if $G_1$ and $G_2$ are cyclic groups, then $G_3 = G_1 \times G_2$ is also a cyclic group with generator $(g_1, g_2)$ or $(g_1, g_3)$.

we can change $C_1 = g_1^r$ in $G_1$ as $C'_1 = (g_1^r, 1_{G_2})$ in $G_3$ and $C_2 = g_2^rg_3^m$ in $G_2$ to $C'_2 = (1_{G_1}, g_2^rg_3^m)$ in $G_3$, now the question is that for the two new elements in $G_3$, the prover knows the coresponding secret and the equality of $r$ in the first and second element. $1_{G_1}$ and $1_{G_2}$ are the identity in group $G_1$ and $G_2$.

using a similiar intuition, we can get

$C'_1 \circ_{G_3} C'_2 = (g_1^r, g_2^rg_3^m) = (g_1, g_2)^r \circ_{G_3} (1_{G_1}, g_3)^m$ $C'^{-1}_1 \circ_{G_3} C'_2 = (g_1^{-r}, g_2^rg_3^m) = (g_1^{-1}, g_2)^r \circ_{G_3} (1_{G_1}, g_3)^m$

where $(g_1, g_2)$, $(1_{G_1}, g_2)$, $(g_1^{-1}, g_2)$ and $(1_{G_1}, g_3)$ are public elements in group $G_3$. Here $\circ_{G_3}$ denotes the operator in $G_3$.

The you can follow the previous intuition to get a similiar protocol in group $G_3$.

Answer 3

There is an attack in the protocol (in case of different groups) where any value $z$ in $C_2$ will pass the proof:

Just replace $x$ with the following $y$ in the protocol (let's say $z=135$):

$y = x ⋅ p_2 ⋅ (p_2^{-1} \mod p_1) + 135 ⋅ p_1 ⋅ (p_1^{−1} \mod p_2)$.