4
$\begingroup$

Given two Pedersen commitments $c_1=g^vh^{r_1}$ and $c_2=g^{(v^2)}h^{r_2}$, where the committed value in $c_2$ is the square of the committed value in $c_1$, is there a way to prove this relation in zero knowledge?

$\endgroup$
4
$\begingroup$

Yes there is - since any NP relation has a zero-knowledge proof of knowledge (assuming any OWF). Here, it's actually a standard and nice exercise, so I will give you a few hints (if you are stuck, I'll give you more hints):

Do you know how to prove knowledge of an opening to a Pedersen commitment? (hint: it's a straightforward generalization of the Schnorr proof of knowledge of a discrete logarithm)

Then if you know the above, the crucial trick is to rewrite $c_1=g^vh^{r_1}$ and $c_2=g^{(v^2)}h^{r_2}$ as $c_1=g^vh^{r_1}$ and $c_2=c_1^vh^{r_2-vr_1}$. Then, use the proof of knowledge of an opening to show knowledge of an opening of both commitments, to the same message ($v$), in different bases ($g$ and $c_1$).

| improve this answer | |
$\endgroup$
  • $\begingroup$ $c_2$ should be rewritten as $c_1^vh^{r_2-vr_1}$ $\endgroup$ – avdav Jan 13 '19 at 3:23
  • $\begingroup$ That's correct, I edited the answer. $\endgroup$ – Geoffroy Couteau Jan 13 '19 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.