Remarks on elliptic curve discrete logarithm problems

作     者：Kanayama, N Kobayashi, T Saito, T Uchiyama, S 

作者机构：Waseda Univ Grad Sch Sci & Engn Tokyo 1690085 Japan NTT Labs Yokosuka Kanagawa 2390847 Japan Telecommun Adv Org Japan Yokohama Kanagawa 2210031 Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (电子信息通信学会汇刊：电子学、通信及计算机科学基础)

年 卷 期：2000年第E83A卷第1期

页      面：17-23页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：elliptic curve discrete logarithm problem MOV algorithm FR algorithm 

摘      要：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, pie show, by experimental results, that the running time of the proposed algorithm is shorter than that of the original FR algorithm.