The lifting problem for the ECDLP and the Selmer rank

The hardness of the elliptic curve discrete logarithm problem (ECDLP) on a finite field is essential for the security of all elliptic curve cryptographic schemes. A number of ways of approaching the solution to the ECDLP on a finite field is known, for example, the MOV attack [7], and the anomalous attack (see [9], [13]). In their paper [2], Cheon et al. proposed an algorithm to solve the ECDLP on prime fields, which is very efficient if we could lift two points to an elliptic curve over ℚ with rank one. In this paper, we investigate the success probability of their method by estimating the Selmer rank of lifted elliptic curves. We note that the Selmer rank means the upper bound of the rank given by the Selmer group (see [11]).