The notion that a quantum computer might someday break bitcoin is quickly gaining ground. That’s because quantum computers are becoming powerful enough to factor large prime numbers, a critical component of bitcoin’s public key cryptography.
Quantum computers rely on what is known as Shor’s algorithm to achieve this feat. Shor’s algorithm dramatically shortens the time required to solve factorization problems. It’s also tailor-made for quantum computing, as it exploits the “superposition” of states used in quantum computing.
Unwinding Public Key Cryptography
The security behind wallet creation and transaction signing is predicated on public-key cryptography. What is public-key cryptography?
Let’s start by noting that Bitcoin’s protocol relies on an Elliptic Curve Digital Signature Algorithm (ECDSA) to create a private key and its corresponding public key. Bitcoin users should know about both.
Public keys employ a hash function to create your bitcoin’s public address (what you send and receive funds with). This public key itself was meant to be shared with other users. The fact that crypto users feel compelled to hide their public key suggests that the key system is inherently flawed.
Private keys are used to sign and validate transactions, and thus are kept secret.
While a user’s public key can be mathematically derived from his/her private key, private keys cannot be derived from public keys. This “one-way function” is dependent on the inability of any classical computer to easily factor large prime numbers.
The Magic of Shor’s Algorithm
In 1994, mathematician Peter Shor revealed a quantum algorithm that can actually derive a private key from a public key. Shor’s algorithm achieves this by reducing the number of steps required to find the prime factors of large numbers.
While a classical computer can reduce any factor problem to a matter of order-finding, it cannot solve the order-finding problem itself. Quantum computers are exceptionally effective at solving this order-finding problem, however. That’s because their speed-up over classical algorithms scales exponentially.
With Shor’s algorithm, anyone with a powerful enough quantum computer – roughly 2300 qubits (source) – can reconstitute a private key from its corresponding public key.
Once a private key is known, an attacker can create a digital signature that is verifiable by its corresponding public key. As you might suspect, this allows an attacker to access a user’s account funds. Depending on the account, the attacker might be able to access additional details about the user as well. Here, identity theft becomes a very real possibility.
Discerning Who Is Vulnerable.
In Bitcoin’s early days, a user’s public key served as their receiving address As a result, anyone conducting a bitcoin transaction could readily view the recipient’s public key.
Cryptography experts soon realized, however, that these ‘pay to public key’ (p2pk) addresses might…