# Several Discrete Logarithm Zero Knowledge Proof

According to Wiki there is an approach for proving knowledge of $$x$$ such that $$g^x = y$$. How can I prove that I know $$x_1, x_2$$ such that $$g^{x_1} = y_1, g^{x_2}=y_2$$. Of course, I can make these proofs separately but I would like to combine them into a single one. My idea is to prove that I know such $$x = x_1 + x_2$$ that $$g^x = y_1 y_2$$. But is it safe? Does not it make the system vulnerable?

But is it safe?

Well, knowledge of $$x_1 + x_2$$ does not imply that you know either $$x_1$$ or $$x_2$$.

On the other hand, if you were to prove knowledge of $$r_1x_1 + r_2x_2$$, for a random (e.g. selected by the verifier or a Random Oracle) $$r_1, r_2$$ values, that would be a zero knowledge proof of knowledge of both $$x_1, x_2$$

This can be done by extending the single-exponent zero knowledge proof in a fairly simple way:

• Prover sends $$g^v$$ to the verifier (for some random $$v$$)

• Verifier sends random $$c, d$$ to the prover

• Prover sends $$r = v - cx_1 - dx_2$$ to verifier

• Verifier accepts if $$g^v = g^r (g^{x_1})^c (g^{x_2})^d$$

• Can $c$ and $d$ be generated via a hash function? Jul 15 at 14:04
• @КириллВолков: yes; for my example, I did the interactive version - it's straight-forward to turn it into a noninteractive protocol Jul 15 at 14:05
• Thank you very much!! Jul 15 at 14:06
• Can I extend the algorithm for $x_1, x_2, x_3, \ldots, x_n$ in the same way? Jul 16 at 5:43
• @КириллВолков: yes, it works in the obvious way. Jul 16 at 11:46