As an apology for my “April Fool’s” blog post, I thought I would present a summary of what is known about algorithms for ECDLP that run in asymptotic time less than the square-root time of Pollard rho.
Let 
Can we do better?
The rest of this article lists some approaches that give ECDLP algorithms with running time better than 
- One can always “unbalance” the baby-step-giant-step algorithm. By using
precomputation and storage one can solve an instance of the ECDLP in an “online” time of
group operations. For example, taking
we have an algorithm that solves each individual instance of the ECDLP in
group operations.
This approach is usually completely impractical, especially due to the storage requirement. But the concept can make sense if one is going to be solving a very large number of instances of the ECDLP in the same (relatively small) group, and it demonstrates that the
- A similar idea can be done for Pollard rho. The precomputation is still enormous, but at least the storage stays small. Bernstein and Lange have analysed this approach (see the papers Computing small discrete logarithms faster and Non-uniform cracks in the concrete). Bernstein and Lange explain that with
precomputation one has can solve individual ECDLP instances in
Again, for practical applications this is not necessarily a serious concern. But in systems where many users work in the same group one should be careful to set security levels that take into account such a scenario (for example, recall the Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice paper, which has too many authors to write down here).
- Brown-Gallant and Cheon have considered variants of the ECDLP where one is given
where
is a point of order
and
. (I assume that
.) They show one can solve this variant of the ECDLP (i.e., compute
) in
group operations. Taking
gives an algorithm with
group operations. There are also algorithms for the case when
, but they need more intermediate group elements.
These methods require that
has a factor of the appropriate size and that auxiliary points such as
are available. Hence, these methods are not a threat to elliptic curve cryptosystems as presently used.
- Semaev introduced summation polynomials in 2004. Gaudry and Diem were quick to realise that they could be combined with Weil descent. Gaudry focussed on the case of
where
is fixed and
goes to infinity. His approach, combined with a “double-large-prime” strategy leads to an algorithm with running time
operations (ignoring log terms). The constant in the running time depends exponentially (at least) in
Taking
we have an algorithm with running time
operations, which is better than the
operations of Pollard rho, and the gap grows as
Returning to my recent hoax: Is there a
ECDLP algorithm? Yes indeed: When
then the running time of Gaudry’s algorithm on
. But the constants are terrible and I am confident that no-one is ever going to perform an experiment of Gaudry’s algorithm in
that beats Pollard rho. I also remark that such curves have never been suggested for ECC in practice.
Diem showed an even stronger result: that there are families of finite fields
for which the ECDLP is subexponential time. But there are no practical implications of this method to elliptic curve cryptosystems.
- Several recent papers have suggested improved results for ECDLP on elliptic curves over extension fields. These methods are all based on summation polynomials.
The papers about ECDLP in characteristic two have been discussed in these two blog posts. These ideas potentially give some speedups to the summation polynomial algorithms, but there is currently little theoretical or experimental evidence to support these claims. The methods do not apply to elliptic curves over prime fields.
Most recently, the paper Algebraic approaches for the Elliptic Curve Discrete Logarithm Problem over prime fields by Christophe Petit, Michiel Kosters and Ange Messeng was published at PKC 2016. This paper has some interesting and original ideas, and it does apply to elliptic curves over prime fields. But there seem to be no serious implications at present for the use of elliptic curves in practice. From a theoretical point of view, the method is unlikely to perform as well as the methods for characterstic 2 fields (of prime degree), and those methods have not been established yet to beat Pollard rho, so there is currently no evidence that the method in the PKC 2016 paper can beat Pollard rho either. Table 4 of the Petit-Kosters-Messeng paper reports on experiments: the new algorithm solves the ECDLP over a 22-bit finite field in around 5000 seconds, compared with Magma’s implementation of baby-step-giant-step which solves the same problem in 0.01 seconds.
— Steven Galbraith
ellipticnews 
What about attacks with pairings? MOV attack / anomalous curves.