Towards better attacks on the elliptic curve discrete logarithm problem

The elliptic curve discrete logarithm problem (ECDLP) is one of the core number theory problems used in cryptography today. In particular, TLS now supports elliptic curve cryptography protocols for both key exchange and authentication. The elliptic curve discrete logarithm problem is believed to be much harder than the discrete logarithm problem over finite fields and the factorization problem, as the best attacks for commonly used parameters are still generic DLP algorithms. As key sizes in applications are chosen accordingly, it is important to understand the exact hardness of ECDLP.

In this talk, we will review existing algorithms to solve ECDLP, with a special focus on index calculus attacks. These attacks have been very successful against other discrete logarithm problems, in particular over finite fields. For elliptic curves, they have also led to L(2/3) algorithms for some particular families (which are however never used in practice). We will describe recent work giving potential generalizations of these attacks to families recommended in standards, including binary curves and prime curves, and we will highlight remaining challenges in their complexity analysis.