Does this research also work for breaking bitcoin ECDSA? If so, how many qubit will be needed for 256-bit elliptic curve key?
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ First, it's unclear if it works at all. This is discussed here. $\endgroup$– fgrieu ♦Commented Jan 14, 2023 at 19:04
-
$\begingroup$ @fgrieu If it works how many qubit is needed? $\endgroup$– user106244Commented Jan 14, 2023 at 19:17
-
2$\begingroup$ Does this answer your question? Quantum Computing Used to Break RSA by "fixing" Schnorr's Recent Factorization Claim? $\endgroup$– Rohit GuptaCommented Jan 15, 2023 at 0:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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...
