Seminar Coding Theory & Cryptography: Claus Diem
Claus Diem, Universität Leipzig
On the discrete logarithm problem in elliptic curves
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 for certain families of finite fields, the discrete logarithm problem in elliptic curves over these fields can also be solved in subexponential expected time.
Location: Grosser Hörsaal