Computing isogenies between supersingular elliptic curves over F_p

DOI10.1007/S10623-014-0010-1zbMATH Open1361.11044DBLPjournals/dcc/DelfsG16arXiv1310.7789OpenAlexW2205392500WikidataQ61914005 ScholiaQ61914005MaRDI QIDQ5963365FDOQ5963365

Steven D. Galbraith, Christina Delfs

Publication date: 19 February 2016

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

elliptic curvesisogeniessupersingular curves

Mathematics Subject Classification ID

Complex multiplication and moduli of abelian varieties (11G15) Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16) Finite ground fields in algebraic geometry (14G15) Elliptic curves (14H52) Isogeny (14K02)

Cites Work

• The Arithmetic of Elliptic Curves
• Title not available (Why is that?)
• Title not available (Why is that?)
• Abelian varieties over finite fields
• Cryptographic hash functions from expander graphs
• Title not available (Why is that?)
• Expander graphs based on GRH with an application to elliptic curve cryptography
• Improved algorithm for the isogeny problem for ordinary elliptic curves
• Constructing Isogenies between Elliptic Curves Over Finite Fields
• Title not available (Why is that?)
• Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves
• Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?
• Title not available (Why is that?)
• A Note on Elliptic Curves Over Finite Fields
• A Rigorous Subexponential Algorithm For Computation of Class Groups
• Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies
• Title not available (Why is that?)

Cited In (58)

• Improved torsion-point attacks on SIDH variants
• \( L_1\)-norm ball for CSIDH: optimal strategy for choosing the secret key space
• Orientations and the supersingular endomorphism ring problem
• Improved supersingularity testing of elliptic curves using Legendre form
• Trapdoor DDH groups from pairings and isogenies
• Rational isogenies from irrational endomorphisms
• Computing $(\ell ,\ell )$-isogenies in polynomial time on Jacobians of genus $2$ curves
• SimS: a simplification of SiGamal
• Towards practical key exchange from ordinary isogeny graphs
• A review of mathematical and computational aspects of CSIDH algorithms
• PERK: compact signature scheme based on a new variant of the permuted kernel problem
• B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion
• Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graphs
• SiGamal: a supersingular isogeny-based PKE and its application to a PRF
• Computational problems in supersingular elliptic curve isogenies
• 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
• Improved classical cryptanalysis of SIKE in practice
• Computing isogenies between elliptic curves over $F_{p^n}$ using Couveignes's algorithm
• Breaking the decisional Diffie-Hellman problem for class group actions using genus theory
• Parallel isogeny path finding with limited memory
• Breaking the decisional Diffie-Hellman problem for class group actions using genus theory: extended version
• Constructing cycles in isogeny graphs of supersingular elliptic curves
• How to construct CSIDH on Edwards curves
• Towards a quantum-resistant weak verifiable delay function
• SQIsignHD: new dimensions in cryptography
• Neighborhood of the supersingular elliptic curve isogeny graph at \(j = 0\) and 1728
• Efficient Algorithms for Supersingular Isogeny Diffie-Hellman
• Supersingular j-invariants and the class number of ℚ(−p)
• On the key generation in $\mathbf{SQISign}$
• Oriented supersingular elliptic curves and Eichler orders of prime level
• Constructing an efficient hash function from $3$-isogenies
• The Supersingular Isogeny Problem in Genus 2 and Beyond
• On the Isogeny Problem with Torsion Point Information
• CSIDH on the Surface
• Cycles in the Supersingular ℓ-Isogeny Graph and Corresponding Endomorphisms
• Threshold schemes from isogeny assumptions
• CSURF-TWO: CSIDH for the ratio \((2:1)\)
• Disorientation faults in CSIDH
• Computing the Brauer group of the product of two elliptic curves over a finite field
• Adventures in Supersingularland
• Accelerating the Delfs-Galbraith algorithm with fast subfield root detection
• Endomorphism rings of supersingular elliptic curves over \(\mathbb{F}_p\)
• Group Key Exchange from CSIDH and Its Application to Trusted Setup in Supersingular Isogeny Cryptosystems
• CSIDH: an efficient post-quantum commutative group action
• New SIDH countermeasures for a more efficient key exchange
• SCALLOP: scaling the CSI-FiSh
• Horizontal racewalking using radical isogenies
• 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
• 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
• 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 a basis of the set of isogenies between two supersingular elliptic curves

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)