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

Question

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$?

Answer 1

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.

Answer 2

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.