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
La sécurité de la cryptographie à courbe elliptique est étroitement liée à la complexité informatique du problème du logarithme discret à courbe elliptique (ECDLP). Aujourd'hui, les meilleures attaques pratiques contre l'ECDLP sont les algorithmes de logarithme discret génériques à temps exponentiel tels que la méthode rho de Pollard. Une récente ligne de recherche sur le calcul d'indices pour l'ECDLP lancée par Semaev, Gaudry et Diem a montré que, sous certaines hypothèses heuristiques, de tels algorithmes pourraient conduire à des attaques subexponentielles contre l'ECDLP. Dans cette étude, nous étudions la complexité informatique de l'ECDLP pour les courbes elliptiques sous diverses formes - notamment les représentations de Hesse, de Montgomery, d'Edwards (tordues) et de Weierstrass - en utilisant le calcul d'indice. À l’aide du calcul d’indice, nous visons à déterminer s’il existe une différence significative dans la complexité de calcul de l’ECDLP pour les courbes elliptiques sous diverses formes. Nous fournissons des preuves empiriques et des informations montrant une réponse affirmative dans cet article.
Chen-Mou CHENG
Osaka University
Kenta KODERA
Osaka University
Atsuko MIYAJI
Osaka University,Japan Advanced Institute of Science and Technology
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
Chen-Mou CHENG, Kenta KODERA, Atsuko MIYAJI, "Differences among Summation Polynomials over Various Forms of Elliptic Curves" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1061-1071, September 2019, doi: 10.1587/transfun.E102.A.1061.
Abstract: The security of elliptic curve cryptography is closely related to the computational complexity of the elliptic curve discrete logarithm problem (ECDLP). Today, the best practical attacks against ECDLP are exponential-time generic discrete logarithm algorithms such as Pollard's rho method. A recent line of inquiry in index calculus for ECDLP started by Semaev, Gaudry, and Diem has shown that, under certain heuristic assumptions, such algorithms could lead to subexponential attacks to ECDLP. In this study, we investigate the computational complexity of ECDLP for elliptic curves in various forms — including Hessian, Montgomery, (twisted) Edwards, and Weierstrass representations — using index calculus. Using index calculus, we aim to determine whether there is any significant difference in the computational complexity of ECDLP for elliptic curves in various forms. We provide empirical evidence and insight showing an affirmative answer in this paper.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1061/_p
Copier
@ARTICLE{e102-a_9_1061,
author={Chen-Mou CHENG, Kenta KODERA, Atsuko MIYAJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Differences among Summation Polynomials over Various Forms of Elliptic Curves},
year={2019},
volume={E102-A},
number={9},
pages={1061-1071},
abstract={The security of elliptic curve cryptography is closely related to the computational complexity of the elliptic curve discrete logarithm problem (ECDLP). Today, the best practical attacks against ECDLP are exponential-time generic discrete logarithm algorithms such as Pollard's rho method. A recent line of inquiry in index calculus for ECDLP started by Semaev, Gaudry, and Diem has shown that, under certain heuristic assumptions, such algorithms could lead to subexponential attacks to ECDLP. In this study, we investigate the computational complexity of ECDLP for elliptic curves in various forms — including Hessian, Montgomery, (twisted) Edwards, and Weierstrass representations — using index calculus. Using index calculus, we aim to determine whether there is any significant difference in the computational complexity of ECDLP for elliptic curves in various forms. We provide empirical evidence and insight showing an affirmative answer in this paper.},
keywords={},
doi={10.1587/transfun.E102.A.1061},
ISSN={1745-1337},
month={September},}
Copier
TY - JOUR
TI - Differences among Summation Polynomials over Various Forms of Elliptic Curves
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1061
EP - 1071
AU - Chen-Mou CHENG
AU - Kenta KODERA
AU - Atsuko MIYAJI
PY - 2019
DO - 10.1587/transfun.E102.A.1061
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - The security of elliptic curve cryptography is closely related to the computational complexity of the elliptic curve discrete logarithm problem (ECDLP). Today, the best practical attacks against ECDLP are exponential-time generic discrete logarithm algorithms such as Pollard's rho method. A recent line of inquiry in index calculus for ECDLP started by Semaev, Gaudry, and Diem has shown that, under certain heuristic assumptions, such algorithms could lead to subexponential attacks to ECDLP. In this study, we investigate the computational complexity of ECDLP for elliptic curves in various forms — including Hessian, Montgomery, (twisted) Edwards, and Weierstrass representations — using index calculus. Using index calculus, we aim to determine whether there is any significant difference in the computational complexity of ECDLP for elliptic curves in various forms. We provide empirical evidence and insight showing an affirmative answer in this paper.
ER -