Skip to main content
edited body
Source Link
Geoffroy Couteau
  • 21.3k
  • 2
  • 50
  • 72

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^{vr_1-r_2}$$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$).

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^{vr_1-r_2}$. 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$).

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$).

Source Link
Geoffroy Couteau
  • 21.3k
  • 2
  • 50
  • 72

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^{vr_1-r_2}$. 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$).