Masaya Yasuda
Fujitsu Laboratories Ltd.
1-1, Kamikodanaka 4-chome, Nakahara-ku, Kawasaki
211-8588, Japan

Abstract. 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 [#!MOV!#], and the anomalous attack (see [#!SSSA!#], [#!Smart!#]). In their paper [#!CLH!#], 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 [#!Silverman!#]).

Received: April 8, 2011

AMS Subject Classification: 11G05, 14H52

Key Words and Phrases: ECDLP, formal groups, the Selmer rank

Download paper from here.