The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.1 pp.17-23

- Publication Date
- 2000/01/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Naoki KANAYAMA, Tetsutaro KOBAYASHI, Taiichi SAITO, Shigenori UCHIYAMA, "Remarks on Elliptic Curve Discrete Logarithm Problems" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 1, pp. 17-23, January 2000, doi: .

Abstract: 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_1_17/_p

Copy

@ARTICLE{e83-a_1_17,

author={Naoki KANAYAMA, Tetsutaro KOBAYASHI, Taiichi SAITO, Shigenori UCHIYAMA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Remarks on Elliptic Curve Discrete Logarithm Problems},

year={2000},

volume={E83-A},

number={1},

pages={17-23},

abstract={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.},

keywords={},

doi={},

ISSN={},

month={January},}

Copy

TY - JOUR

TI - Remarks on Elliptic Curve Discrete Logarithm Problems

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 17

EP - 23

AU - Naoki KANAYAMA

AU - Tetsutaro KOBAYASHI

AU - Taiichi SAITO

AU - Shigenori UCHIYAMA

PY - 2000

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E83-A

IS - 1

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - January 2000

AB - 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.

ER -