For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Remarks on Elliptic Curve Discrete Logarithm Problems
Naoki KANAYAMA Tetsutaro KOBAYASHI Taiichi SAITO Shigenori UCHIYAMA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/01/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
elliptic curve discrete logarithm problem, MOV algorithm, FR algorithm,
Full Text: PDF(449.9KB)>>
The MOV and FR algorithms, which are representative attacks on elliptic curve cryptosystems, reduce the elliptic curve discrete logarithm problem (ECDLP) to the discrete logarithm problem in a finite field. This paper studies these algorithms and introduces the following three results. First, we show an explicit condition under which the MOV algorithm can be applied to non-supersingular elliptic curves. Next, by comparing the effectiveness of the MOV algorithm to that of the FR algorithm, it is explicitly shown that the condition needed for the MOV algorithm to be subexponential is the same as that for the FR algorithm except for elliptic curves of trace two. Finally, a new explicit reduction algorithm is proposed for the ECDLP over elliptic curves of trace two. This algorithm differs from a simple realization of the FR algorithm. Furthermore, we show, by experimental results, that the running time of the proposed algorithm is shorter than that of the original FR algorithm.