Constructing elliptic curve isogenies in quantum subexponential time
Speaker: Professor Andrew Childs, University of Waterloo, Ontario, Canada
Series: Topical Seminars
Location:
Bowen Hall Auditorium
Date/Time: Monday, December 13, 2010, 12:30 p.m.
- 1:30 p.m.
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 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.
