IEICE TRANSACTIONS on Fundamentals
Differences among Summation Polynomials over Various Forms of Elliptic Curves
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1061-1071
- Publication Date
- 2019/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E102.A.1061
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Cryptography and Information Security
Authors
Chen-Mou CHENG
Osaka University
Kenta KODERA
Osaka University
Atsuko MIYAJI
Osaka University,Japan Advanced Institute of Science and Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
