01598nas a2200157 4500008004100000245007300041210006900114260001500183300001100198490000600209520112600215100002301341700001501364700002401379856003701403 2014 eng d00aConstructing elliptic curve isogenies in quantum subexponential time0 aConstructing elliptic curve isogenies in quantum subexponential c2014/01/01 a1 - 290 v83 a Given two elliptic curves over a finite field having the same cardinality and
endomorphism ring, it is known that the curves admit an 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 subexponential-time quantum
algorithm for constructing isogenies, assuming the Generalized Riemann
Hypothesis (but with no other assumptions). Our algorithm is based on a
reduction to a hidden shift problem, together with a new subexponential-time
algorithm for evaluating isogenies from kernel ideals (under only GRH), and
represents the first nontrivial application of Kuperberg's quantum algorithm
for the hidden shift problem. This result suggests that isogeny-based
cryptosystems may be uncompetitive with more mainstream quantum-resistant
cryptosystems such as lattice-based cryptosystems.
1 aChilds, Andrew, M.1 aJao, David1 aSoukharev, Vladimir uhttp://arxiv.org/abs/1012.4019v2