Constructing elliptic curve isogenies in quantum subexponential time
By Andrew M. Childs, David Jao, Vladimir Soukharev. Journal of Mathematical Cryptology, 2010
303 citations recorded by the source corpus.
Abstract. Given two ordinary elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit a nonzero isogeny between them, but finding such an isogeny is believed to be computationally difficult. The fastest known classical algorithm takes exponential time, and prior to our work no faster quantum algorithm was known. Recently, public-key cryptosystems based on the presumed hardness of this problem have been proposed as candidates for post-quantum cryptography. In this paper, we give a new subexponential-time quantum algorithm for constructing nonzero isogenies between two such elliptic curves, assuming the Generalized Riemann Hypothesis (but with no other assumptions). Our algorithm is based on a reduction to a hidden shift problem, and represents the first nontrivial application of Kuperberg's quantum algorithm for finding hidden shifts. This result suggests that isogeny-based cryptosystems may be uncompetitive with more mainstream quantum-resistant cryptosystems such as lattice-based cryptosystems. As part of this work, we also present the first classical algorithm for evaluating isogenies having provably subexponential running time in the cardinality of the base field under GRH.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems
View Paper: https://www.semanticscholar.org/paper/cecdb3b5e9097878ffd9fd87a48e19cdae344896
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Tiago M. Fernández-Caramés
- Paula Fraga-Lamas
- Tanja Lange
- Lorenz Panny
- Joost Renes
- Wouter Castryck
- Chloe Martindale
In Computational Theory and Mathematics
In Information Systems
Citations in the corpus
- Towards Post-Quantum Blockchain: A Review on Blockchain Cryptography Resistant to Quantum Computing Attacks (2020, methodology): “These schemes are based on the isogeny protocol for ordinary elliptic curves presented in [124], but enhanced to withstand the quantum attack detailed in [125].”
- CSIDH: An Efficient Post-Quantum Commutative Group Action (2018, methodology): “The relevance of these quantum algorithms to Problem 10 has been observed by Childs–Jao–Soukharev [12] in the ordinary case and by Biasse–Jao–Sankar [4] in the supersingular setting.”