如何高效查找兩個EC點私鑰之間的距離
存在兩個 EC 私鑰 $ x_1 $ 和 $ x_2 $ , 其中它們對應的公鑰在眾所周知的基點上 $ G $ 是 $ X_1=x_1G $ 和 $ X_2=x_2G $ 分別。生成的循環群的順序為 $ G $ 是 $ \ell $ .
選擇了那些私鑰，使得距離 $ d=|x_1-x_2|\ (mod\ \ell) $ 小於 $ 2^n $ , 對於聲明價值 $ n $ .
給定 $ X_1 $ ，我們如何確定 $ d $ 比重複加/減更有效 $ G $ 至 $ X_1 $ 直到匹配到 $ X_2 $ ?
我們可以使用Baby-step/giant-step的小變體來查找 $ d $ 按順序 $ 3,2^{n/2} $ 點加法（和正規化到唯一的點表示）。我們從嬰兒步 $ X_1 $ , 和巨大的步驟從 $ X_2 $ （在後面的兩個方向上，以補償未知的符號 $ x_1-x_2 $ ）。它是這樣的：
讓 $ m=\lceil2^{n/2}\rceil $
讓 $ W_0:=X_1 $
為了 $ i $ 從 $ 1 $ 至 $ m-1 $ （嬰兒步）
- 放 $ W_i=W_{i-1}+G $
注意：這裡 $ W_i=X_1+i,G $
讓 $ H=m,G $ （可以得到 $ H=W_{m-1}+G-W_0 $ )
讓 $ U:=X_2 $ 和 $ V:=X_2-H $
讓 $ j=0 $
重複（巨大的步驟）
注意：這裡 $ U=X_2+(j,m),G $ 和 $ V=X_2-((j+1),m),G $
- 如果 $ U $ 被發現在 $ W_i $
- 輸出 $ |j,m-i| $ 並停止
- 如果 $ V $ 被發現在 $ W_i $
- 輸出 $ (j+1),m+i $ 並停止
- 讓 $ U:=U+H $ 和 $ V:=V-H $
- 讓 $ j:=j+1 $
如果遵循註釋中所述的條件，則該算法始終以輸出停止 $ d $ 大約之後 $ d/2^{n/2} $ （最多 $ m $ ) 重複循環的迭代。請注意，使用適當的資料結構，搜尋的成本 $ U $ 和 $ V $ 在表中 $ W_i $ 基本上是恆定的 $ n $ ，因此主要的計算成本是點加法（以及它們的結果的正規化，因此 $ W_i $ 可以有效地搜尋）。
問題是，這需要大量記憶體用於 $ W_i $ ，並且所述算法是順序的。這可以通過使用 Paul C. van Oorschot 和 Michael J. Wiener 的Parallel Collision Search with Cryptanalytic Applications（密碼學雜誌，1999 年）中的技術來解決，並且搜尋分佈在多台機器上。