Let E be an elliptic curve over $\mathbb{Q}$. Is there an efficient algorithm which can solve an elliptic curve discrete logarithm in E?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ you can probably take advantage of the height pairing to produce a quick algorithm. $\endgroup$– zebCommented Dec 12, 2013 at 10:13
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
10
As Joro says, you can use the height pairing. And it's worth pointing out that it is generally possible to compute canonical heights even when the coefficients of $E$ are so large that it's infeasible to factor the discriminant.
- Computing canonical heights with little (or no) factorization, Math. Comp. 66 (1997), 787-805.
In particular, it should be possible even on curves whose coefficients are of cryptographic size.
It's also possible to solve ECDLP over a global field using ideas based on the proof of the weak Mordell-Weil theorem. I briefly discuss this in
- Lifting and elliptic curve discrete logarithms, Selected Areas of Cryptography (SAC 2008), Lecture Notes in Computer Science 5381, Springer--Verlag, Berlin, 2009, 82-102.
answered Dec 12, 2013 at 12:58
-
$\begingroup$ How better is this than bruteforce? The naive height grows quite fast, so one can't explicitly compute $k P$ for $k$ large enough. $\endgroup$– joroCommented Dec 12, 2013 at 13:20
-
$\begingroup$ It is very efficient. One computes the logarithmic canonical height $\hat h(P)$ as a sum of local heights $\lambda_\infty(P)+\sum_p\lambda_p(P)$. There is a fast-converging series for $\lambda_\infty(P)$ due to Tate that let's you compute it to (say) 100 decimal places in a fraction of a second. The $p$-adic contributions are generally even easier to compute (as described in my paper). Note that one isn't computing $kP$; instead one computes $\hat h(Q)/\hat h(P)$, takes the square root, and rounds to the nearest integer. $\endgroup$ Commented Dec 12, 2013 at 14:00
-
$\begingroup$ Hmmmm... I guess that if $k$ has a couple of hundred digits, you'll need to compute the heights to (say) 100,000 decimal places. That should still be feasible, but probably requires several minutes (or even hours?) of computer time. But Tate's series looks like $\sum A_k$ with $|A_k|=O(1/4^k)$, so converges quite rapidly. And there's an even faster converging method that using AGMs. $\endgroup$ Commented Dec 12, 2013 at 14:04
-
1$\begingroup$ No, you absolutely cannot explicitly compute $10^{10}P$, if by compute you mean write down its coordinates as rational numbers, since its coordinates have numerators and denominators with on the order of $10^{100}$ binary digits! OTOH, we can easily write down $\hat h(10^{10}P)$ to (say) 10000 decimal digits. This is no different from the fact that you cannot explicitly write down the integer $3^{100}$, but you can easily compute its logarithm to 10000 decimal places. ... $\endgroup$ Commented Dec 12, 2013 at 15:26
-
1$\begingroup$ The discrete logarithm problem is to find $m$ so that $Q=mP$. But you're right in the sense that it's not possible to explicitly pose an ECDLP over $\mathbb{Q}$ in which $m\approx10^{10}$ by writing down the coordinates of $P$ and $Q$ as rational numbers. $\endgroup$ Commented Dec 12, 2013 at 15:54
$\begingroup$
$\endgroup$
Yes, it is related to the canonical height (assuming you can handle large points).
Here is a sage session:
sage: E=EllipticCurve(QQ,[1,1,1,1,0]);P=E(0,0);k=9;Q=k*P
sage: sqrt(Q.height()/P.height())
9.00000000000000
If $H(P)$ is the canonical height and $Q= k P$, $k=\sqrt{H(Q)/H(P)}$
