|
Friday, Nov 19, 2010 |
|
|
|
|
Constructing Elliptic Curve Isogenies in Quantum Subexponential Time |
|
|
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. |