Join Log in
Score:3
knaccc avatar Crypto

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

es flag
knaccc

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

134
0 + 0
Score:2
Berry Schoenmakers avatar Crypto
bd flag
Berry Schoenmakers

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.

0 + 0
Score:2
fgrieu avatar Crypto
ng flag
fgrieu

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.

0 + 0
cn flag
Maeher
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.
1
Reply
knaccc avatar
es flag
knaccc
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.
1
Reply
fgrieu avatar
ng flag
fgrieu
@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$.
0
Reply
knaccc avatar
es flag
knaccc
@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.
1
Reply
fgrieu avatar
ng flag
fgrieu
@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$.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.