Post
Topic
Board Development & Technical Discussion
Re: Mining scripts on quantum computers
by
Cnut237
on 07/02/2021, 09:30:27 UTC
The quantum Shor algorithm is a much more powerful approach than Grover, and can be used to destroy public-key cryptography.
~snip

This only works on RSA keypairs (and any other cryptosystem that uses prime factoring) and it is inapplicable to the elliptic curve cryptography that Bitcoin uses.

Elliptic curves take their private key as an extremely large number and multiply that by a curve point to get the public key. It's completely different from getting two primes and multiplying together to derive the private key, public key and other parameters, which is what Shor's algorithm applies to.

I think address re-use is the key point. If you are using a one-time address, then the QC needs to derive the private address in the time between the transaction being sent and it being accepted. But if you are re-using an address, then Shor on a sufficiently powerful QC can derive the private key in 128^3=2,097,152 steps, compared with 2^128=340,282,366,920,938,463,463,374,607,431,768,211,456 steps on a classical computer. ECC is vulnerable to Shor.