The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Les algorithmes MOV et FR, qui sont des attaques représentatives sur les cryptosystèmes à courbe elliptique, réduisent le problème du logarithme discret à courbe elliptique (ECDLP) au problème du logarithme discret dans un corps fini. Cet article étudie ces algorithmes et présente les trois résultats suivants. Tout d’abord, nous montrons une condition explicite sous laquelle l’algorithme MOV peut être appliqué à des courbes elliptiques non supersingulaires. Ensuite, en comparant l'efficacité de l'algorithme MOV à celle de l'algorithme FR, il est explicitement montré que la condition nécessaire pour que l'algorithme MOV soit sous-exponentiel est la même que celle de l'algorithme FR, à l'exception des courbes elliptiques de la trace deux. Enfin, un nouvel algorithme de réduction explicite est proposé pour l'ECDLP sur les courbes elliptiques de la trace deux. Cet algorithme diffère d'une simple réalisation de l'algorithme FR. De plus, nous montrons, par des résultats expérimentaux, que le temps d'exécution de l'algorithme proposé est plus court que celui de l'algorithme FR original.
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.
Copier
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
Copier
@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},}
Copier
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 -