Do all elliptic curves of the same order have the same difficulty of discrete log?

David Jao, Stephen D. Miller, Ramarathnam Venkatesan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Scopus citations

Abstract

The aim of this paper is to justify the common cryptographic practice of selecting elliptic curves using their order as the primary criterion. We can formalize this issue by asking whether the discrete log problem (DLOG) has the same difficulty for all curves over a given finite field with the same order. We prove that this is essentially true by showing polynomial time random reducibility of DLOG among such curves, assuming the Generalized Riemann Hypothesis (GRH). We do so by constructing certain expander graphs, similar to Ramanujan graphs, with elliptic curves as nodes and low degree isogenies as edges. The result is obtained from the rapid mixing of random walks on this graph. Our proof works only for curves with (nearly) the same endomorphism rings. Without this technical restriction such a DLOG equivalence might be false; however, in practice the restriction may be moot, because all known polynomial time techniques for constructing equal order curves produce only curves with nearly equal endomorphism rings.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - ASIACRYPT 2005 - 11th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Pages21-40
Number of pages20
DOIs
StatePublished - Dec 1 2005
Event11th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2005 - Chennai, India
Duration: Dec 4 2005Dec 8 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3788 LNCS

Other

Other11th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2005
CountryIndia
CityChennai
Period12/4/0512/8/05

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Discrete log
  • Elliptic curves
  • Expanders
  • Generalized Riemann hypothesis
  • Isogenies
  • L-functions
  • Modular forms
  • Ramanujan graphs
  • Random reducibility
  • Rapid mixing

Fingerprint Dive into the research topics of 'Do all elliptic curves of the same order have the same difficulty of discrete log?'. Together they form a unique fingerprint.

  • Cite this

    Jao, D., Miller, S. D., & Venkatesan, R. (2005). Do all elliptic curves of the same order have the same difficulty of discrete log? In Advances in Cryptology - ASIACRYPT 2005 - 11th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 21-40). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3788 LNCS). https://doi.org/10.1007/11593447_2