Computing isogenies between supersingular elliptic curves over F_p
From MaRDI portal
Publication:5963365
Abstract: Let p>3 be a prime and let E, E' be supersingular elliptic curves over F_p. We want to construct an isogeny phi: E --> E'. The currently fastest algorithm for finding isogenies between supersingular elliptic curves solves this problem by performing a "meet-in-the-middle" breadth-first search in the full supersingular 2-isogeny graph over F_{p^2}. In this paper we consider the structure of the isogeny graph of supersingular elliptic curves over F_p. We give an algorithm to construct isogenies between such supersingular elliptic curves that works faster than the usual algorithm. We then discuss how this results can be used to obtain an improved algorithm for the general supersingular isogeny problem.
Recommendations
- Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graphs
- Constructing supersingular elliptic curves
- The supersingular isogeny problem in genus 2 and beyond
- Constructing supersingular elliptic curves with a given endomorphism ring
- Fast algorithms for computing isogenies between elliptic curves
Cites work
- scientific article; zbMATH DE number 5663802 (Why is no real title available?)
- scientific article; zbMATH DE number 4006420 (Why is no real title available?)
- scientific article; zbMATH DE number 45834 (Why is no real title available?)
- scientific article; zbMATH DE number 706265 (Why is no real title available?)
- scientific article; zbMATH DE number 2086697 (Why is no real title available?)
- scientific article; zbMATH DE number 3356934 (Why is no real title available?)
- A Note on Elliptic Curves Over Finite Fields
- A Rigorous Subexponential Algorithm For Computation of Class Groups
- Abelian varieties over finite fields
- Constructing Isogenies between Elliptic Curves Over Finite Fields
- Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves
- Cryptographic hash functions from expander graphs
- Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?
- Expander graphs based on GRH with an application to elliptic curve cryptography
- Improved algorithm for the isogeny problem for ordinary elliptic curves
- The Arithmetic of Elliptic Curves
- Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies
Cited in
(70)- On isogeny graphs of supersingular elliptic curves over finite fields
- On the hardness of the computational ring-LWR problem and its applications
- Quantum lattice enumeration and tweaking discrete pruning
- \( L_1\)-norm ball for CSIDH: optimal strategy for choosing the secret key space
- Endomorphism rings of supersingular elliptic curves over \(\mathbb{F}_p\)
- Orientations and the supersingular endomorphism ring problem
- Cycles in the Supersingular ℓ-Isogeny Graph and Corresponding Endomorphisms
- Identifying supersingular elliptic curves
- Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graphs
- Constructing cycles in isogeny graphs of supersingular elliptic curves
- Improved supersingularity testing of elliptic curves using Legendre form
- CSIDH: an efficient post-quantum commutative group action
- Trapdoor DDH groups from pairings and isogenies
- SimS: a simplification of SiGamal
- Breaking the decisional Diffie-Hellman problem for class group actions using genus theory: extended version
- Constructing supersingular elliptic curves with a given endomorphism ring
- Efficient Algorithms for Supersingular Isogeny Diffie-Hellman
- The supersingular isogeny problem in genus 2 and beyond
- Neighborhood of the supersingular elliptic curve isogeny graph at \(j = 0\) and 1728
- Computing $(\ell ,\ell )$-isogenies in polynomial time on Jacobians of genus $2$ curves
- Supersingular j-invariants and the class number of ℚ(−p)
- Threshold schemes from isogeny assumptions
- CSURF-TWO: CSIDH for the ratio \((2:1)\)
- Algebraic approaches for solving isogeny problems of prime power degrees
- On the isogeny problem with torsion point information
- Improved classical cryptanalysis of SIKE in practice
- Rational isogenies from irrational endomorphisms
- Implementation report of the Kohel-Lauter-Petit-Tignol algorithm for the constructive Deuring correspondence
- Disorientation faults in CSIDH
- Loops of isogeny graphs of supersingular elliptic curves at \(j=0\)
- How to construct CSIDH on Edwards curves
- Computing newforms using supersingular isogeny graphs
- Constructing an efficient hash function from \(3\)-isogenies
- Computing isogenies between elliptic curves over $F_{p^n}$ using Couveignes's algorithm
- Accelerating the Delfs-Galbraith algorithm with fast subfield root detection
- Adventures in Supersingularland
- On the key generation in $\mathbf{SQISign}$
- Computing supersingular isogenies on Kummer surfaces
- Breaking the decisional Diffie-Hellman problem for class group actions using genus theory
- SCALLOP: scaling the CSI-FiSh
- A quantum algorithm for computing isogenies between supersingular elliptic curves
- SiGamal: a supersingular isogeny-based PKE and its application to a PRF
- Parallel isogeny path finding with limited memory
- CSIDH on the surface
- Computational problems in supersingular elliptic curve isogenies
- Horizontal racewalking using radical isogenies
- On the cost of computing isogenies between supersingular elliptic curves
- Supersingular curves with small noninteger endomorphisms
- Group Key Exchange from CSIDH and Its Application to Trusted Setup in Supersingular Isogeny Cryptosystems
- Towards practical key exchange from ordinary isogeny graphs
- B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion
- Improved torsion-point attacks on SIDH variants
- Improved algorithms for finding fixed-degree isogenies between supersingular elliptic curves
- QFESTA: efficient algorithms and parameters for FESTA using quaternion algebras
- Radical \(\sqrt[N]{\text{élu}}\) isogeny formulae
- Computing the Brauer group of the product of two elliptic curves over a finite field
- A review of mathematical and computational aspects of CSIDH algorithms
- New SIDH countermeasures for a more efficient key exchange
- An effective lower bound on the number of orientable supersingular elliptic curves
- Towards a quantum-resistant weak verifiable delay function
- SQIsignHD: new dimensions in cryptography
- On the feasibility of computing constructive Deuring correspondence
- An algorithm for efficient detection of \((N, N)\)-splittings and its application to the isogeny problem in dimension 2
- AprèsSQI: extra fast verification for SQIsign using extension-field signing
- Isogeny problems with level structure
- Adding level structure to supersingular elliptic curve isogeny graphs
- Oriented supersingular elliptic curves and Eichler orders of prime level
- Finding orientations of supersingular elliptic curves and quaternion orders
- Computing a basis of the set of isogenies between two supersingular elliptic curves
- PERK: compact signature scheme based on a new variant of the permuted kernel problem
This page was built for publication: Computing isogenies between supersingular elliptic curves over \(\mathbb {F}_p\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963365)
