0
$\begingroup$

Assuming that x has a sqrt.

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

$\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 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 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 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 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 at 17:18
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.