×

Constructing elliptic curve isogenies in quantum subexponential time. (English) Zbl 1283.81046

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.

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

Software:

NTRUEncrypt
PDFBibTeX XMLCite
Full Text: DOI arXiv