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?


1 Answer 1


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$

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

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.