Tutte seminar - David Jao

Constructing Elliptic Curve Isogenies in Quantum Subexponential Time

Abstract:

Given two elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit an isogeny (a.k.a. algebraic map) between them, but finding such an isogeny is believed to be computationally difficult. The fastest known classical algorithm for this problem requires exponential time, and prior to our work no faster quantum algorithm was known. We show that this problem can be solved in subexponential time on a quantum computer, assuming the Generalized Riemann Hypothesis (and no other assumptions). Our result indicates that public-key cryptosystems based on isogenies may not be as quantum-resistant as previously believed. As part of our work, we also obtain a second result of independent interest: given an isogeny between curves of equal endomorphism ring, we show how to evaluate the isogeny in subexponential time, assuming (only) GRH, eliminating the heuristic assumptions required by prior algorithms. 

Joint work with Andrew Childs and Vladimir Soukharev.