Assuming that x has a sqrt.
Given $P=xG$ is it possible to prove that I know the $sqrt(x)$ in zero knowledge?
$\begingroup$
$\endgroup$
-
1$\begingroup$ Is the group of prime order? If so it's trivial to compute the square root and it would suffice to prove knowledge of $x$. $\endgroup$ – SEJPM♦ Jun 12 '19 at 15:38
-
$\begingroup$ @SEJPM Yep, it's a group of prime order. If I've given the verifier P, how would I convince him that I know the sqrt(x) without sending it to him? After I computer it, what would I do? $\endgroup$ – WeCanBeFriends Jun 12 '19 at 15:43
-
$\begingroup$ Hi, WeCanBeFriends, and welcome to Cryptography Stack Exchange. I notice that you've been posting several questions today that look like homework assignments. Please note that, while asking questions arising from homework is not forbidden here, this site is not a do-my-homework service, and questions consisting of just a problem statement with no context are likely to get closed. $\endgroup$ – Ilmari Karonen Jun 12 '19 at 16:05
-
$\begingroup$ @IlmariKaronen Got it. They are not homework problems, just questions that I find interesting, and have run into dead-ends with. $\endgroup$ – WeCanBeFriends Jun 12 '19 at 16:07
-
1$\begingroup$ @SEJPM: yes, it's trivial to compute square-roots of quadratic residues, however not all group members are quadratic residues. You would also need to prove that the $x$ you know is one... $\endgroup$ – poncho Jun 12 '19 at 17:18
$\begingroup$
$\endgroup$
My answer simply extends the comment by SEJPM.
Since the group has prime order (as you said in the comment), and since you assume that it is known that $x$ has a square root, you can simply prove knowledge of $x$ such that $xG = P$, using the standard Schnorr protocol for demonstrating knowledge of a discrete logarithm (see e.g. the wikipedia page, or my description here for a simplified security analysis of this protocol).
Now, since knowing $x$ is equivalent to knowing $\sqrt{x}$ in a group of prime order (each can be computed from the other in polynomial time), convincing the verifier that you know $x$ does also convince him that you know $\sqrt{x}$. Since the proof leaks nothing about $x$, it leaks nothing about $\sqrt{x}$.
answered Jun 17 '19 at 10:30
