According to Google's Quantum AI team, a future quantum computer could potentially derive a bitcoin private key from a public key in approximately nine minutes. This revelation sent shockwaves through social media and the markets, but what are the practical implications? To understand this, let's examine how bitcoin transactions work.
When a bitcoin transaction is made, the wallet uses a private key to sign the transaction, which is a secret number confirming ownership of the coins. This signature also reveals the public key, a shareable address that is broadcast to the network and awaits confirmation in the mempool. On average, this confirmation process takes around 10 minutes.
The link between the private and public keys is based on a complex mathematical problem known as the elliptic curve discrete logarithm problem, which classical computers cannot solve within a useful timeframe. However, a sufficiently powerful quantum computer utilizing the Shor's algorithm could potentially reverse this math. The recent paper found that a quantum computer could be pre-programmed to pre-compute parts of the attack that are not dependent on a specific public key.
Once a public key appears in the mempool, the quantum computer would only need about nine minutes to derive the private key. Given that bitcoin's average confirmation time is 10 minutes, this gives the attacker a roughly 41% chance of succeeding in redirecting funds before the original transaction is confirmed. This scenario can be likened to a thief creating a universal safe-cracking machine that, once built, only needs minor adjustments to crack any safe, with these adjustments taking about nine minutes.
The more pressing concern, however, is the approximately 6.9 million bitcoin that are already vulnerable due to exposed public keys. These include early bitcoin addresses and wallets that have reused addresses, thereby revealing the public key.
Such coins are at risk of being cracked by a sufficiently powerful quantum computer without any time pressure. The 2021 Taproot upgrade inadvertently expanded the pool of vulnerable wallets.
While the bitcoin network would continue to function, as mining uses a different algorithm that quantum computers cannot significantly speed up, the ability to derive private keys from public keys would undermine the ownership guarantees that give bitcoin its value. The solution lies in transitioning to post-quantum cryptography, which would replace the current vulnerable math with quantum-resistant algorithms.
Ethereum has been working towards this migration for eight years, whereas bitcoin has yet to begin this process.