3
$\begingroup$

How long exactly would it take for a regular computer to crack an elliptic curve public/private key via bruteforce, vs. a quantum computer using Shor's algorithm with a couple thousand qubits? Can anyone reference me a source?

I'm assuming the digital computer will take thousands of years, but how long exactly is the polynomial time achieved by theoretical quantum computers?

$\endgroup$
1
$\begingroup$

It's hard to answer given that there is no quantum computer to perform benchmark on. However, let us assume a quantum computer which would perform quantum operations as efficiently as our current standard computer can perform classical operations (this might be a bit unrealistic but it's hard to come out with realistic assumptions regarding quantum computing given the state of advancement of this research field). The complexity of Shor's algorithm being $O(\log^2 n \log \log n \log \log \log n)$ according to Wikipedia, one can observe that this is better than the complexity of the best known classical algorithms for performing the multiplication of two $\log n \times \log n$ matrices. A quick search over some papers such as this one indicates that an optimized implementation of matrix multiplication of size $1024\times 1024$ can take less than a second, hence it does not seem unreasonable to assume that if a quantum computer was executing an optimized implementation of Shor's algorithm, factorization of a 2048 bit integer would take very little time - say, less than a few minuts.

For a regular computer performing a discrete logarithm over an elliptic curve is not done with brute force as you suggest, but using the Rho-Pollard algorithm, whose complexity is $O(\sqrt{p})$, where $p$ is the order of the curve. Still, executing this algorithm on well-chosen curves of size higher than $256$ bits is completely impractical.

$\endgroup$
  • 3
    $\begingroup$ "Still, executing this algorithm on well-chosen curves of size higher than 256 bits would take at least several years". Eh, sorry, but who's choosing the curves here? $\sqrt p$ where $p = 2^{256}$ would still leave you with $2^{128}$ right? Are you saying that you expect that to run "at least several years" on classical computers? And if so, are you employed by the NSA? $\endgroup$ – Maarten Bodewes May 17 '16 at 22:59
  • $\begingroup$ Sorry, I wrote incorrectly what I had in mind - I was thinking about $256$ bit being the size of $\sqrt{p}$, not of $p$, and performing the computation on a standard computer. Durations I mentioned are rough estimation, feel free to indicate more correct estimations. I do not have much relation with NSA yet :) $\endgroup$ – Geoffroy Couteau May 17 '16 at 23:12
  • 1
    $\begingroup$ @GeoffroyCouteau, I think the point was that even $2^{128}$ is "at least several decades if it can be done", rather than a few years. $2^{256}$ is pretty much just "never". Also, why are you talking about integer factorization, when the question was about elliptic curves? $\endgroup$ – otus May 18 '16 at 14:09
  • $\begingroup$ Well whatever, my point was simply that this is completely impractical currently, I've not done any concrete estimation for this part of the question. Not sure I understand the NSA part too :) Shor's algorithm can be used either for discrete logarithm or for factorization, and the complexity I had in mind was related to the case where it's used for factoring some modulus $n$. For such a question, we're just talking about very rough estimations, so my point was just a comparison between Shor's algorithm and the complexity of matrix multiplication. $\endgroup$ – Geoffroy Couteau May 18 '16 at 15:11
  • $\begingroup$ "... hence it does not seem unreasonable to assume that if a quantum computer was executing an optimized implementation of Shor's algorithm, factorization of a 2048 bit integer would take very little time - say, less than a few minut[e]s..." How does that possibly follow from the asymptotic complexity of Shor's algorithm? $\endgroup$ – Aleph Jun 17 '16 at 16:43

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.