# How to efficiently find the distance between two EC point private keys

There exist two EC private keys $$x_1$$ and $$x_2$$, where their corresponding public keys on the well-known base point $$G$$ are $$X_1=x_1G$$ and $$X_2=x_2G$$ respectively. The order of the cyclic group generated by $$G$$ is $$\ell$$.

Those private keys have been chosen such that the distance $$d=|x_1-x_2|\ (mod\ \ell)$$ is less than $$2^n$$, for a declared value of $$n$$.

Given $$X_1$$, how can we determine $$d$$ more efficiently than by just repeatedly adding/subtracting $$G$$ to $$X_1$$ until there is a match with $$X_2$$?

We can use a minor variant of Baby-step/giant-step to find $$d$$ with in the order of $$3\,2^{n/2}$$ point additions (and normalization to a unique point representation). We make baby steps from $$X_1$$, and giant steps from $$X_2$$ (in both directions for the later, to compensate for the unknown sign of $$x_1-x_2$$). Here it goes:

• let $$m=\lceil2^{n/2}\rceil$$
• let $$W_0:=X_1$$
• for $$i$$ from $$1$$ to $$m-1$$ (Baby steps)
• set $$W_i=W_{i-1}+G$$
note: here $$W_i=X_1+i\,G$$
• let $$H=m\,G$$ (which can be obtained as $$H=W_{m-1}+G-W_0$$ )
• let $$U:=X_2$$ and $$V:=X_2-H$$
• let $$j=0$$
• repeat (Giant steps)
note: here $$U=X_2+(j\,m)\,G$$ and $$V=X_2-((j+1)\,m)\,G$$
• if $$U$$ is found in the $$W_i$$
• output $$|j\,m-i|$$ and stop
• if $$V$$ is found in the $$W_i$$
• output $$(j+1)\,m+i$$ and stop
• let $$U:=U+H$$ and $$V:=V-H$$
• let $$j:=j+1$$

If follows from the conditions stated in notes that this algorithm always stops with output $$d$$ after about $$d/2^{n/2}$$ (at most $$m$$) iterations of the repeat loop. Notice that using an appropriate data structure, the cost of the searches of $$U$$ and $$V$$ in the table of $$W_i$$ is essentially constant w.r.t. $$n$$, thus the main computational cost is the point additions (and the normalization of their result so that the $$W_i$$ can be searched efficiently).

Problems are, this requires a lot of memory for the table of $$W_i$$, and the algorithm as stated is sequential. This can be solved, and the search distributed among several machines, by using the techniques in Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

• This answers the question in the body, but not the question in the title, because the suggested algorithm is more efficient but certainly not actually efficient. Feb 13, 2022 at 13:08
• Thanks, I implemented your method and it works perfectly! When n=24, I'm getting a speed-up of around 100x vs the naive method. Feb 13, 2022 at 19:30
• @knaccc: for n=24 I would be expecting a speed-up by a factor like 1000, for an efficient data structure searching for $U$ and $V$ in the $W_i$.
– fgrieu
Feb 14, 2022 at 6:25
• @fgrieu I think it's because the EC library I'm using gives the results of additions/subtractions in P3 co-ordinate space (XYZT), and so either there will be overhead from field element multiplications to normalize the Z co-ord prior to P3 to P3 comparison, or alternatively there will be field element ops required to convert from P3 to a single signed coordinate for the purposes of single-co-ordinate comparison. Feb 14, 2022 at 7:37
• @knaccc: ah that makes sense. If it's faster by a large factor $\alpha$ to test for a point addition having reached the neutral than it is to make a normalized point representation as necessary for search, then the expected speedup is reduced by a factor near $\alpha$.
– fgrieu
Feb 14, 2022 at 7:48

You can use baby-step giant-step or rather Pollard's lambda (or, kangaroo) algorithm to find $$d$$ using $$O(2^{n/2})$$ group operations, which will outperform your linear search of roughly $$2^n$$ group operations if $$n$$ is not too small.