Elliptic curves were first proposed as a tool for cryptography by V. Miller in 1985 [29]. Indeed, since elliptic curves have a group structure, they nicely fit as a replacement for more traditional groups in discrete logarithm based systems such as Diffie-Hellman or ElGamal. Moreover, since there is no non-generic algorithm for computing discrete logarithms on elliptic curves, it is possible to reach a high security level while using relatively short keys.