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?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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$).
answered Dec 20 '18 at 1:39
-
$\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
