Constructing elliptic curve isogenies in quantum subexponential time

Journal of mathematical cryptology

article

Andrew Childs¹  David Jao²  Vladimir Soukharev² 

[1] Department of Combinatorics & Optimization and Institute for Quantum Computing, University of Waterloo;Department of Combinatorics & Optimization, University of Waterloo

关键词: Elliptic curves;    isogenies;    hidden shift problem;    quantum algorithms;   

DOI  :  10.1515/jmc-2012-0016

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

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.

【 授权许可】

CC BY|CC BY-NC-ND