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.
In this article, the authors consider the problem of constructing an isogeny between two supersingular elliptic curves defined over \(\mathbb{F}_p\) (\(p>3\)). The fastest known algorithm to do this solves the problem in the isogeny graph of cardinality \(O(p)\) of all supersingular curves over \({\mathbb{F}}_{p^2}\) using a meet-in-the-middle search and runs in \(\tilde{O}(p^{1/2})\) (the notation \(\tilde{O}\) means forgetting about logarithmic factors). The present idea is to use the fact that both curves are defined over \(\mathbb{F}_p\) to find a path in a graph which looks more like the ordinary case graph and which has only \(\tilde{O}(p^{1/2})\) elements, hence a complexity of \(\tilde{O}(p^{1/4})\). In order to provide the algorithm, the authors rely on the classical results of [\textit{W. C. Waterhouse}, Ann. Sci. Éc. Norm. Supér. (4) 2, 521--560 (1969; Zbl 0188.53001)] to derive the structure of the graph, in particular a minimal set of isogeny degrees which make the graph connected.
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
- 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
- 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?)
- 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
(96)- On isogeny graphs of supersingular elliptic curves over finite fields
- Quantum lattice enumeration and tweaking discrete pruning
- On the hardness of the computational ring-LWR problem and its applications
- Towards practical key exchange from ordinary isogeny graphs
- CSIDH: an efficient post-quantum commutative group action
- Computing supersingular isogenies on Kummer surfaces
- On the cost of computing isogenies between supersingular elliptic curves
- Computational problems in supersingular elliptic curve isogenies
- Algebraic approaches for solving isogeny problems of prime power degrees
- Constructing cycles in isogeny graphs of supersingular elliptic curves
- Threshold schemes from isogeny assumptions
- Improved classical cryptanalysis of SIKE in practice
- CSURF-TWO: CSIDH for the ratio \((2:1)\)
- Implementation report of the Kohel-Lauter-Petit-Tignol algorithm for the constructive Deuring correspondence
- Breaking the decisional Diffie-Hellman problem for class group actions using genus theory
- Computing newforms using supersingular isogeny graphs
- SimS: a simplification of SiGamal
- Rational isogenies from irrational endomorphisms
- Improved torsion-point attacks on SIDH variants
- Orientations and the supersingular endomorphism ring problem
- Neighborhood of the supersingular elliptic curve isogeny graph at j = 0 and 1728
- Endomorphism rings of supersingular elliptic curves over \(\mathbb{F}_p\)
- Loops of isogeny graphs of supersingular elliptic curves at \(j=0\)
- Breaking the decisional Diffie-Hellman problem for class group actions using genus theory: extended version
- L₁-norm ball for CSIDH: optimal strategy for choosing the secret key space
- B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion
- SiGamal: a supersingular isogeny-based PKE and its application to a PRF
- Efficient Algorithms for Supersingular Isogeny Diffie-Hellman
- Constructing supersingular elliptic curves with a given endomorphism ring
- A quantum algorithm for computing isogenies between supersingular elliptic curves
- Constructing an efficient hash function from 3-isogenies
- Cycles in the Supersingular ℓ-Isogeny Graph and Corresponding Endomorphisms
- Constructing Isogenies between Elliptic Curves Over Finite Fields
- Computing isogenies between elliptic curves over $F_{p^n}$ using Couveignes's algorithm
- Group Key Exchange from CSIDH and Its Application to Trusted Setup in Supersingular Isogeny Cryptosystems
- CSIDH on the surface
- The supersingular isogeny problem in genus 2 and beyond
- On the isogeny problem with torsion point information
- Identifying supersingular elliptic curves
- Computing (\ell ,\ell )-isogenies in polynomial time on Jacobians of genus 2 curves
- Supersingular curves with small noninteger endomorphisms
- Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graphs
- Supersingular j-invariants and the class number of ℚ(−p)
- How to construct CSIDH on Edwards curves
- SCALLOP: scaling the CSI-FiSh
- Disorientation faults in CSIDH
- Accelerating the Delfs-Galbraith algorithm with fast subfield root detection
- Adventures in Supersingularland
- Horizontal racewalking using radical isogenies
- Parallel isogeny path finding with limited memory
- On the key generation in $\mathbf{SQISign}$
- On the feasibility of computing constructive Deuring correspondence
- Computing the Brauer group of the product of two elliptic curves over a finite field
- New SIDH countermeasures for a more efficient key exchange
- A review of mathematical and computational aspects of CSIDH algorithms
- PERK: compact signature scheme based on a new variant of the permuted kernel problem
- An effective lower bound on the number of orientable supersingular elliptic curves
- Towards a quantum-resistant weak verifiable delay function
- Oriented supersingular elliptic curves and Eichler orders of prime level
- Finding orientations of supersingular elliptic curves and quaternion orders
- An algorithm for efficient detection of \((N, N)\)-splittings and its application to the isogeny problem in dimension 2
- SQIsignHD: new dimensions in cryptography
- 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
- QFESTA: efficient algorithms and parameters for FESTA using quaternion algebras
- Radical \(\sqrt[N]{\text{élu}}\) isogeny formulae
- Improved algorithms for finding fixed-degree isogenies between supersingular elliptic curves
- Computing a basis of the set of isogenies between two supersingular elliptic curves
- Cycles and cuts in supersingular L-isogeny graphs
- Efficient algorithms for the detection of (N, N)-splittings and endomorphisms
- The Lang-Trotter conjecture on average for genus-2 curves with Klein-4 reduced automorphism group
- Multiple group action dlogs with(out) precomputation
- PRISM: simple and compact identification and signatures from large prime degree isogenies
- SQIsign2D-West. The fast, the small, and the safer
- Ideal-to-isogeny algorithm using 2-dimensional isogenies and its application to SQIsign
- SILBE: an updatable public key encryption scheme from lollipop attacks
- On random sampling of supersingular elliptic curves
- Neighborhood of vertices in the isogeny graph of principally polarized superspecial abelian surfaces
- Computing supersingular endomorphism rings using inseparable endomorphisms
- Endomorphism rings of supersingular elliptic curves over \(\mathbb{F}_p\) and binary quadratic forms
- Higher-degree supersingular group actions
- Efficient supersingularity testing over \(\mathbb{F}(p)\) and CSIDH key validation
- Supersingular non-superspecial abelian surfaces in cryptography
- The spine of a supersingular -isogeny graph
- Evaluation of modular polynomial from supersingular elliptic curves
- Tate-Shafarevich groups of constant elliptic curves and isogeny volcanoes
- SQIsign2DPush: faster signature scheme using 2-dimensional isogenies
- WaterSQI and PRISMO: quaternion signatures for supersingular isogeny group actions
- The SEA algorithm for endomorphisms of supersingular elliptic curves
- Endomorphisms via splittings
- The supersingular endomorphism ring problem given one endomorphism
- On the (non-)existence of efficient class group orbits for collision search in CSIDH
- Attacks on PRISM-id via torsion over small extension fields
- Improved supersingularity testing of elliptic curves using Legendre form
- Trapdoor DDH groups from pairings and isogenies
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)
