Childs, Andrew; Jao, David; Soukharev, Vladimir Constructing elliptic curve isogenies in quantum subexponential time. (English) Zbl 1283.81046 J. Math. Cryptol. 8, No. 1, 1-29 (2014). Summary: 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. Cited in 1 ReviewCited in 65 Documents MSC: 81P94 Quantum cryptography (quantum-theoretic aspects) 68Q12 Quantum algorithms and complexity in the theory of computing 11Y40 Algebraic number theory computations 14H52 Elliptic curves 81P68 Quantum computation Keywords:elliptic curves; isogenies; hidden shift problem; quantum algorithms Software:NTRUEncrypt PDFBibTeX XMLCite \textit{A. Childs} et al., J. Math. Cryptol. 8, No. 1, 1--29 (2014; Zbl 1283.81046) Full Text: DOI arXiv