Andrew Childs, Institute for Quantum Computing
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. Recently, public-key cryptosystems based on this problem have been proposed as potentially resistant to quantum attacks. We give a quantum algorithm for constructing isogenies that runs in subexponential time assuming the Generalized Riemann Hypothesis (and with no other heuristic assumptions). This result suggests that isogeny-based cryptosystems may be uncompetitive with more mainstream alternatives such as lattice-based cryptography.
Based on joint work with David Jao and Vladimir Soukharev.