# Given $P=xG$, prove in zero knowledge that I know $sqrt(x)$

Assuming that x has a sqrt.

Given $$P=xG$$ is it possible to prove that I know the $$sqrt(x)$$ in zero knowledge?

• 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$. – SEJPM Jun 12 at 15:38
• @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? – WeCanBeFriends Jun 12 at 15:43
• 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. – Ilmari Karonen Jun 12 at 16:05
• @IlmariKaronen Got it. They are not homework problems, just questions that I find interesting, and have run into dead-ends with. – WeCanBeFriends Jun 12 at 16:07
• @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... – poncho Jun 12 at 17:18

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