# Proving Sigma Protocol on a Schnorr Protocol Variant

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).

• To prove this, you need Sigma definition, and then you show that it fits the definition. Take a look at "Rethinking PKI" book (in pdf) on credentica.com – Vadym Fedyukovych Apr 30 '17 at 8:36
• @VadymFedyukovych I understand I have to show: Completeness, Soundness and Honest-Verifier Zero Knowledge. However I'm not sure how. – Jjang Apr 30 '17 at 18:57
• Great. Completeness is.. – Vadym Fedyukovych Apr 30 '17 at 20:56

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$$.