On the Progress of Elliptic Curve Discrete Logarithm Problem

Since 1985 when elliptic curve cryptography was proposed, its theory and applications have attracted a wide spread attention. The hardness of the discrete logarithm problem in elliptic curves is crucial for the security of elliptic curve cryptosystems. Since the fastest algorithms for the discrete problem in generic elliptic curves are exponential, smaller key sizes can provide the same level of security as other public-key cryptosystems.This advantage is attractive for applications where the computational power and storage space are limited, and numerous standards organizations have standardized elliptic curve cryptographic approach for public-key encryption, key agreement and digital signature. Additionally, it is easy to construct elliptic curves which are suitable for cryptographic applications by using Schoof's algorithm and complex multiplication algorithm. Normally elliptic curves considered for cryptographic application are defined over binary or prime fields. For potential performance advantages, various forms of extension fields have been proposed for usage. However, some elliptic curves over finite non-prime fields can be attacked with index calculus based on summation polynomials and Weil descent attack, which are faster than the generic algorithms. Consequently, for cryptographic purposes, it is necessary to study the security reduction these algorithms lead to and find features weak curves share. This survey describes the state-of-the-art in algorithms for solving the elliptic curve discrete logarithm problem.