2
$\begingroup$

Is it possible to prove that a point on an elliptic curve falls within a given range of another point, without revealing the distance between them. For example:

Let's say $X$ and $Y$ are two points on an elliptic curve such that $X = x \cdot G$ and $Y = y \cdot G$, where $G$ is the generator. The proover knows values of $x$ and $y$, and wants to prove to the verifier that $|x - y| < z$, where $z$ is some value supplied by the verifier.

Another option: prove that $\frac{x}{y} < z$, where $z$ can be a relatively small number (e.g. 2).

Is either of these possible?

$\endgroup$
  • $\begingroup$ Two step Yao's Millionaires' problem? $\endgroup$ – kelalaka Dec 23 '18 at 12:40
2
$\begingroup$

The proof showing that, given $G$ and $x \cdot G$ and a range $[A,B]$, $x$ is in the range $[A,B]$ is known as the range proof. In your case, we can convert your statement as the range proof as, given $G$ and $H = xG - yG$, showing $x-y$ is in the range $[-z,z]$.

For example, the following papers (and a lot of papers) proposed efficient range proofs.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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