Rational Isogenies from Irrational Endomorphisms
- 1 May 2020
- book chapter
- Published by Springer Nature
- Vol. 12106, 523-548
Abstract
In this paper, we introduce a polynomial-time algorithm to compute a connecting \(\mathcal {O}\)-ideal between two supersingular elliptic curves over \(\mathbb {F}_p\) with common \(\mathbb {F}_p\)-endomorphism ring \(\mathcal {O}\), given a description of their full endomorphism rings. This algorithm provides a reduction of the security of the CSIDH cryptosystem to the problem of computing endomorphism rings of supersingular elliptic curves. A similar reduction for SIDH appeared at Asiacrypt 2016, but relies on totally different techniques. Furthermore, we also show that any supersingular elliptic curve constructed using the complex-multiplication method can be located precisely in the supersingular isogeny graph by explicitly deriving a path to a known base curve. This result prohibits the use of such curves as a building block for a hash function into the supersingular isogeny graph.
Keywords
This publication has 20 references indexed in Scilit:
- Computing isogenies between supersingular elliptic curves over ${\mathbb {F}}_p$ F pDesigns, Codes and Cryptography, 2014
- Elligator2013
- Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies2011
- Algorithmic Enumeration of Ideal Classes for Quaternion OrdersSIAM Journal on Computing, 2010
- Cryptographic Hash Functions from Expander GraphsJournal of Cryptology, 2007
- Easy Decision Diffie-Hellman GroupsLMS Journal of Computation and Mathematics, 2004
- On the computation of quadratic $2$-class groupsJournal de Théorie des Nombres de Bordeaux, 1996
- Lattice basis reduction: Improved practical algorithms and solving subset sum problemsMathematical Programming, 1994
- Explicit bounds for primality testing and related problemsMathematics of Computation, 1990
- A rigorous subexponential algorithm for computation of class groupsJournal of the American Mathematical Society, 1989