On the discrete logarithm problem in elliptic curves

Claus Diem (University of Leipzig)

Thursday 29 November 2012, 15.00, b-it 1.25 (cosec meeting room)

It is well known that the classical discrete logarithm problem, that is, the problem to compute discrete logarithms in multiplicative groups of prime fields, can be solved in subexponential expected time. The same holds for the discrete logarithm problem in the multiplicative groups of all finite fields.

The corresponding algorithms are based on the so-called index calculus method which roughly speaking consists of relation generation and linear algebra.

About 25 years ago, N. Koblitz and V. Miller suggested to consider the discrete logarithm problem in elliptic curves over finite fields for cryptographic application. The main motivation was that it should be very difficult to apply the index calculus method to these groups successfully.

In the talk, I will show that nonetheless, the index calculus method can be applied successfully to the discrete logarithm problem in elliptic curves over finite non-prime fields. I will argue that over certain families of finite fields, the elliptic curve discrete logarithm problem can also be solved in subexponential expected time.