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

  • $\begingroup$ 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 $\endgroup$ Commented Apr 30, 2017 at 8:36
  • $\begingroup$ @VadymFedyukovych I understand I have to show: Completeness, Soundness and Honest-Verifier Zero Knowledge. However I'm not sure how. $\endgroup$
    – Jjang
    Commented Apr 30, 2017 at 18:57
  • $\begingroup$ Great. Completeness is.. $\endgroup$ Commented Apr 30, 2017 at 20:56

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


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.