Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?

DOI10.1007/11593447_2MaRDI QIDQ5451062zbMATH OpenOpenAlexFDO

Authors David D. Yao, Stephen D. Miller, Ramarathnam Venkatesan

Publication date 18 March 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0411378

zbMATH Keywords

\(L\)-functionsdiscrete logelliptic curvesexpandersgeneralized Riemann hypothesisisogeniesmodular formsRamanujan graphsrandom reducibilityrapid mixing

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cryptography (94A60)

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.

Recommendations

• scientific article; zbMATH DE number 697834
• Solving the multi-discrete logarithm problems over a group of elliptic curves with prime order
• On the discrete logarithm problem in elliptic curves
• scientific article; zbMATH DE number 1186977
• scientific article; zbMATH DE number 1302788

Cited in

(19)

• Expander graphs based on GRH with an application to elliptic curve cryptography
• Avoiding side-channel attacks by computing isogenous and isomorphic elliptic curves
• Isolated elliptic curves and the MOV attack
• MOV attack in various subgroups on elliptic curves
• Isogenies on twisted Hessian curves
• Elliptic curve cryptography: the serpentine course of a paradigm shift
• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Solving the multi-discrete logarithm problems over a group of elliptic curves with prime order
• Analogues of Vélu's formulas for isogenies on alternate models of elliptic curves
• Ramanujan graphs in cryptography
• Fast algorithms for computing isogenies between elliptic curves
• Improved algorithm for the isogeny problem for ordinary elliptic curves
• A subexponential algorithm for evaluating large degree isogenies
• Identification protocols and signature schemes based on supersingular isogeny problems
• Computing isogenies between supersingular elliptic curves over \(\mathbb {F}_p\)
• Climbing and descending tall isogeny volcanos
• Isogeny graphs of ordinary abelian varieties
• New types of formula for isogenies between elliptic curves
• Recent progress on the elliptic curve discrete logarithm problem

This page was built for publication: Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5451062)