Proving that two points on elliptic curve are within range

Question

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?

Answer 1

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.

• Jan Camenisch, Rafik Chaabouni, and abhi shelat: Efficient Protocols for Set Membership and Range Proofs (ASIACRYPT 2008)
• Benedikt Bünz and Jonathan Bootle and Dan Boneh and Andrew Poelstra and Pieter Wuille and Greg Maxwell: Bulletproofs: Short Proofs for Confidential Transactions and More (IEEE S&P 2018)