Proving Sigma Protocol on a Schnorr Protocol Variant

Question

Let p, q be chosen as in Schnorr's protocol, and let $g_1, g_2, h$ be elements in $Z^*_P$ of order q.

Assume that the prover P gets as input $w_1,w_2$ where $h = (g_1^{w_1}g_2^{w_2}) \mod q$.

Consider the following protocol:

a) P chooses $r_1,r_2$ at random in $Z_q$ and sends $a = (g_1^{r_1}g_2^{r_2}) \mod q$ to V .

b) V chooses a challenge e at random in $[0,2^t-1]$ and sends it to P.
Here, t is fixed such that $2^t < q$.

c) P sends $z_1 = (r_1 + e*w_1) \mod q$, and $z_2 = (r_2 + e*w_2) \mod q$ to V , who checks that $g_1^{z_1}g_2^{z_2} = (a*h^e) \mod q$, that p and q are prime and that $g_1, g_2$ and h have order q, and accepts iff this is the case.

I need to prove that this is a Sigma-protocol for the relation $h = g_1^{w_1}g_2^{w_2}$ (in the description of the relation, it is understood that it should also be satisfied that p and q are prime, $w_1,w_2$ are in $Z_q$, and that $g_1, g_2$ and $h$ are in $Z^*_p$ and have order q).

Answer 1

This Sigma protocol is basically a variant of the Schnorr knowledge of exponent protocol but with respect to two different generators. Therefore, also the proof is really similar to the classic one:

• Completeness

This is kind of straightforward: $$g_1^{z_1}g_2^{z_2}=g_1^{r_1+ew_1}g_2^{r_2+ew_2}=g_1^{r_1}g_2^{r_2}g_1^{ew_1}g_2^{ew_2}=g_1^{r_1}g_2^{r_2}(g_1^{w_1}g_2^{w_2})^e =ah^e \mod q $$

• Special soundness

Let's assume we have two accepting transcripts $(a,e,(z_1,z_2))$ and $(a,e^{'},(z^{'}_1,z^{'}_2))$. A knowledge extractor could extract the witness in the following way. We have that:

$$g_1^{z_1}g_2^{z_2} = ah^e$$ and $$g_1^{z_1^{'}}g_2^{z_2^{'}} = ah^{e^{'}}$$ Let's divide the two equations and we will get: $g_1^{z_1-z_1^{'}}g_2^{z_2-z_2^{'}} = h^{e-e^{'}}$, which yields: $$g_1^{\frac{z_1-z_1^{'}}{e-e^{'}}}g_2^{\frac{z_2-z_2^{'}}{e-e^{'}}} = h=g_1^{w_1}g_2^{w_2}$$. Therefore the extractor has that $w_1=\frac{z_1-z_1^{'}}{e-e^{'}} \mod q$ and $w_2=\frac{z_2-z_2^{'}}{e-e^{'}} \mod q$ .

• Honest-Verifier zero-knowledge (HVZK)

Let's build the simulator given a random $(z_1,z_2)$ and $e$. The first message message $a$ can be obtained by $a=h^{-e}g_1^{z_1}g_2^{z_2} \mod q$. Clearly, $(a,e,(z_1,z_2))$ have the same distribution as in a real run. Namely, random values satisfying $g_1^{z_1}g_2^{z_2} = ah^e$.