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 someday be exploited. In 2010, bitcoin users began replacing their p2pk addresses with ‘pay to pubkey hash’ (p2pkh) addresses (still used today).
Not incidentally, reused p2pkh addresses should not be considered safe either. Once someone transfers funds from a p2pkh address, their public key becomes public. Consequently, many wallets currently prevent users from reusing an address.
Altogether, roughly a quarter of all bitcoins remain in these two types of addresses (p2pk and reused p2pkh). These coins will eventually become highly vulnerable to theft, as anyone with a powerful quantum computer will be able to calculate the private key from such an address.
While most bitcoin investors no longer use p2pk addresses, they remain vulnerable to them anyway. Once a quantum computer publicly derives a private key from a public key, bitcoin’s price will most likely crash.
Transaction Hijacking
An attacker who can perform a (live) transaction hijacking will need to achieve several tasks in short order. After running Shor’s algorithm to derive the private key, the attacker must then create, sign, and broadcast the conflicting transaction.
All of these steps can be achieved in short order if a powerful quantum computer is present. The outcome will be similar to a double-spending attack, with the exception that the attacker is the sole beneficiary.
An enterprising miner can combine this transaction hijacking attack with a selfish mining attack. Given enough quantum computing power, a miner could create their own secret chain and selectively publish blocks to the public chain.
By doing so, the quantum attacker will cause a reorganization of the public chain (a rolling back of the chain). In this scenario, the attacker acquires all funds and block rewards contained in any transactions spent -- in the now overwritten transactions.
Taproot and Public Key Visibility
Bitcoin users seeking to keep their transactions private might be stymied by companies like Glassnode and Chain Analysis. These companies access and compile the logs from a node’s mempool, viewing the public keys for each transaction in the process.
Public keys may soon be made public again anyway. A bitcoin upgrade named Taproot aims to make all public keys visible on the blockchain. The basis for this upgrade is to make bitcoin transactions more flexible (such as enabling the use of new signature types).
By making public keys visible, of course, Taproot will increase bitcoin’s quantum vulnerability. Critics question the justification for such an upgrade since bitcoin primarily functions as a store of value.
No Easy Solutions
Given these challenges, it seems justifiable to mandate that all bitcoins move to a new p2pkh address. Aside from the legal complications this might entail, it's unlikely to serve as a long-term solution.
Quantum computers will eventually become fast enough to overcome p2pkh protections as well. Instead, instituting quantum-resistant cryptography appears to be the most viable option for meeting this challenge.
Quantum Resistant Ledger (QRL) is playing an instrumental role in this process. The cryptocurrency incorporates a quantum-resistant hash-based signature scheme named XMSS (eXtended Merkle Signature Scheme). If necessary, QRL can also update this signature scheme without compromising its security.
QRL did not simply create a standalone post-quantum blockchain, however. It also created enQlave, an ethereum wallet that secures any ether or erc20 token balance from quantum theft. This innovation incorporates XMSS signature verification on ethereum.
Peter Waterland founded QRL after concluding that quantum computers pose a mortal threat to cryptocurrencies.
Concluding Note
Attempting to fix these problems before quantum computers arrive is a bit heady. It's analogous to rebuilding a car engine while the engine is running and moving downhill. At the bottom of the hill, the car will drive over a cliff if you don’t finish in time. Implementing Taproot is akin to having the throttle stuck open at the same time.
Bitcoin investors who believe that quantum computing remains a distant threat risk being blindsided by the technology.
Quantum computing has already advanced rapidly, far faster than what many scientists had predicted. And since tech companies continue to pour millions of dollars into research and development, nothing can be taken for granted.
For cryptocurrency investors intent on taking a proactive approach toward blockchain security, solutions that feature post-quantum cryptography appear to be their best long-term bet.
At present, Quantum Resistant Ledger is the only blockchain company credibly moving in this direction. Join the discussion about the future of post quantum cryptography today in our discord channel.
See more from Benzinga
© 2021 Benzinga.com. Benzinga does not provide investment advice. All rights reserved.
