Does this research also work for breaking bitcoin ECDSA? If so, how many qubit will be needed for 256-bit elliptic curve key?


1 Answer 1


Does this research also work for breaking bitcoin ECDSA?

No, for two reasons:

  • It doesn't solve a problem that can be used to compute elliptic curve discrete logs.

    The quantum routine they suggest finds relations between smooth numbers (modulo N); given enough of these relations, you can factor N. The insight this relies on is that given a value, we have a nontrivial probability of expressing it as the product of a small set of fixed values (a "factor base"). That's nice, however no one knows of a way to use that as a subroutine to compute discrete logs over an elliptic curve group - we have no known way to express an elliptic curve point in terms of a factor base (with nontrivial probability).

  • It's not clear if it's better than classical methods for solving that problem.

    As mentioned here, it's not clear if it's an improvement over classical methods. After all, we have classical algorithms for generating such relations (which the factoring algorithms QFS and NFS are based on); from the preliminary numbers cited in the paper, the algorithm they give appears to perform not as well as existing algorithms. Now, they ran their algorithm only on comparatively small numbers (because of the limits they had on the size of the available quantum computer), and it's possible (given the lack of theory on how their algorithm behaves as the numbers grow larger) - however, that's not how I'd bet...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.