On the discrete logarithm problem in elliptic curves

Abstract

We study the elliptic curve discrete logarithm problem over finite extension fields. We show that for any sequences of prime powers (q_i)_i∈ℕand natural numbers (n_i)_i∈ℕwithn_i⟶∞andn_i/log (q_i)⟶0 fori⟶∞, the elliptic curve discrete logarithm problem restricted to curves over the fields 𝔽_{q^{niican be solved in subexponential expected time (qnii)o(1). We also show that there exists a sequence of prime powers (qi)i∈ℕsuch that the problem restricted to curves over 𝔽qican be solved in an expected time ofe}}