2
$\begingroup$

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 ?

$\endgroup$
  • 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 Peikert Feb 25 '15 at 0:58
  • $\begingroup$ Do you have source for this? $\endgroup$ – user13741 Mar 18 '15 at 14:47
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.