A subexponential algorithm for evaluating large degree isogenies
From MaRDI portal
Abstract: An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous best known algorithm has a worst case running time which is exponential in the length of the input. In this paper we show this problem can be solved in subexponential time under reasonable heuristics. Our approach is based on factoring the ideal corresponding to the kernel of the isogeny, modulo principal ideals, into a product of smaller prime ideals for which the isogenies can be computed directly. Combined with previous work of Bostan et al., our algorithm yields equations for large degree isogenies in quasi-optimal time given only the starting curve and the kernel.
Recommendations
- Evaluating Large Degree Isogenies and Applications to Pairing Based Cryptography
- Fast algorithms for computing isogenies between elliptic curves
- Explicit isogenies in quadratic time in any characteristic
- Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic
- Improved algorithm for the isogeny problem for ordinary elliptic curves
Cites work
- A Deterministic Algorithm for Solving n = fu 2 + gυ 2 in Coprime Integers u and υ
- A Probabilistic Factorization Algorithm with Quadratic Forms of Negative Discriminant
- A Rigorous Subexponential Algorithm For Computation of Class Groups
- A taxonomy of pairing-friendly elliptic curves
- An elliptic curve trapdoor system
- Binary quadratic forms. An algorithmic approach
- Computing modular polynomials in quasi-linear time
- Computing the endomorphism ring of an ordinary elliptic curve over a finite field
- Constructing Isogenies between Elliptic Curves Over Finite Fields
- Counting points on elliptic curves over finite fields
- Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?
- Endomorphisms of Abelian varieties over finite fields
- Evaluating Large Degree Isogenies and Applications to Pairing Based Cryptography
- Fast algorithms for computing isogenies between elliptic curves
- Handbook of Elliptic and Hyperelliptic Curve Cryptography
- scientific article; zbMATH DE number 435565 (Why is no real title available?)
- scientific article; zbMATH DE number 45834 (Why is no real title available?)
- scientific article; zbMATH DE number 1273650 (Why is no real title available?)
- scientific article; zbMATH DE number 2086697 (Why is no real title available?)
- scientific article; zbMATH DE number 2086892 (Why is no real title available?)
- scientific article; zbMATH DE number 799763 (Why is no real title available?)
- Modular polynomials via isogeny volcanoes
- Topics in Cryptology – CT-RSA 2004
Cited in
(21)- Generalization of Vélu's formulae for isogenies between elliptic curves
- Quantum lattice enumeration and tweaking discrete pruning
- Isolated elliptic curves and the MOV attack
- Towards practical key exchange from ordinary isogeny graphs
- Towards isogeny-based password-authenticated key establishment
- Algebraic approaches for solving isogeny problems of prime power degrees
- Subexponential time relations in the class group of large degree number fields
- Analogues of Vélu's formulas for isogenies on alternate models of elliptic curves
- Subexponential class group and unit group computation in large degree number fields
- Explicit isogenies in quadratic time in any characteristic
- Fast heuristic algorithms for computing relations in the class group of a quadratic order, with applications to isogeny evaluation
- Fast algorithms for computing isogenies between elliptic curves
- Evaluating Large Degree Isogenies and Applications to Pairing Based Cryptography
- Improved algorithm for the isogeny problem for ordinary elliptic curves
- Computing isogeny volcanoes of composite degree
- Pairing the volcano
- Estimating isogenies on tangent spaces
- Explicit Isogenies of Prime Degree Over Quadratic Fields
- Fast and Frobenius: rational isogeny evaluation over finite fields
- Isogeny problems with level structure
- Climbing and descending tall isogeny volcanos
This page was built for publication: A subexponential algorithm for evaluating large degree isogenies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4931651)
