Is there a quantum algorithm to find private keys generated using elliptic curves ?

  • 1
    $\begingroup$ The problem as you ask it is difficult to answer, because you do not specify which private-public key generation algorithms you mean. But as far as I know, in general quantum computers can break discrete log, which most standard elliptic curve algorithms are based on. So, in general, the answer is that there is such a quantum algorithm. $\endgroup$ – A.B. Nov 25 '17 at 10:56
  • $\begingroup$ @A.B. Is it not sufficiënt to say that the private-public key algirithm is bases on elliptic curves? Do you mean that I should specify which elliptic curve? $\endgroup$ – user0009 Nov 25 '17 at 14:43

Shor's algorithm, which runs only on quantum computers, solves all discrete-logarithm problem instances over all groups.

This obviously includes the elliptic curve discrete logarithm problem at the heart of ECDH, ECDSA and ECIES. For a more detailed discussion of the details, see this recent paper.

However, there are things we can do with elliptic curves that are believed to which we don't know better quantum algorithms, like elliptic curve supersingular isogeny-based key exchanges.

  • $\begingroup$ The wiki only mentions Shor's algorithm for integer factorisation, it should also mention all discrete logarithm problems then ? $\endgroup$ – user0009 Nov 26 '17 at 8:31

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.