This was a statement made during a talk at today's DFN-CERT conference but unfortunately it wasn't explained further. Can anyone shed light on why elliptic curves are susceptible to quantum based attacks ?
2
-
4$\begingroup$ The discrete logarithm problem in any cyclic group is easy to solve by quantum algorithms. Elliptic curves merely give a particular choice of cyclic group. Solving the discrete log problem is enough to break all elliptic curve cryptosystems. $\endgroup$– Chris PeikertCommented Feb 25, 2015 at 0:58
-
$\begingroup$ Do you have source for this? $\endgroup$– user13741Commented Mar 18, 2015 at 14:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The elliptic curve discrete logarithm—like integer factorization and the classic finite field discrete logarithm—is an instance of the abelian hidden subgroup problem.
Any abelian (commutative) instance of the hidden subgroup problem can be efficiently solved in quantum computers with (variants of) the Shor algorithm; therefore all of the above problems would be rendered weak if large enough quantum computers were actually built. Here is a concrete polynomial-time quantum attack for the elliptic curve discrete logarithm. See also this question.
