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   Vol.E83-A   No.1   pp.17-23
Publication Date: 2000/01/25
Online ISSN: 
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)>>
Buy this Article

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.