Constructing elliptic curve isogenies in quantum subexponential time

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.

给定在一个有限域上的两条具有相同基数和自同态环的普通椭圆曲线，已知这些曲线之间存在一个非零的同源，但找到这样一个同源被认为在计算上是困难的。已知最快的经典算法需要指数时间，并且在我们的工作之前，没有更快的量子算法被知晓。最近，基于这个问题的假定难度的公钥密码系统已被提议作为后量子密码学的候选方案。在本文中，我们给出了一个新的亚指数时间量子算法，用于在两条这样的椭圆曲线之间构建非零同源，假设广义黎曼假设成立（但没有其他假设）。我们的算法基于对一个隐藏移位问题的归约，并且代表了库珀伯格用于寻找隐藏移位的量子算法的第一个非平凡应用。这个结果表明，基于同源的密码系统可能与更主流的抗量子密码系统（如基于格的密码系统）相比没有竞争力。作为这项工作的一部分，我们还给出了第一个经典算法，用于在广义黎曼假设下，在基域的基数上评估具有可证明的亚指数运行时间的同源。