Differences among summation polynomials over various forms of elliptic curves

Chen Mou Cheng, Kenta Kodera, Atsuko Miyaji

Research output: Contribution to journalJournal Article peer-review

1 Scopus citations

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.

Original languageEnglish
Pages (from-to)1061-1071
Number of pages11
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
VolumeE102A
Issue number9
DOIs
StatePublished - 2019
Externally publishedYes

Bibliographical note

Publisher Copyright:
Copyright © 2019 The Institute of Electronics, Information and Communication Engineers.

Keywords

  • ECDLP
  • Index calculus
  • Point decomposition problem
  • Security evaluation
  • Summation polynomial

Fingerprint

Dive into the research topics of 'Differences among summation polynomials over various forms of elliptic curves'. Together they form a unique fingerprint.

Cite this