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$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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, 2018 at 1:39
-
1$\begingroup$ $c_2$ should be rewritten as $c_1^vh^{r_2-vr_1}$ $\endgroup$– avdavCommented Jan 13, 2019 at 3:23
-
$\begingroup$ That's correct, I edited the answer. $\endgroup$ Commented Jan 13, 2019 at 14:08
-
$\begingroup$ Just to clarify, if we use $v'=v\cdot e+z$ as one of the opening values in the Pedersen proof when $g$ is a base, we need to use this same opening $v'$ when we do it in the second proof when $c_1$ is the base - is that correct? $\endgroup$– SandstarCommented Dec 15, 2023 at 6:47
-
1$\begingroup$ Yes, exactly, and then you adapt the opening of the randomness accordingly to satisfy the verification equations. $\endgroup$ Commented Dec 15, 2023 at 8:50