Is Quantum Computing a Real Threat to Blockchain?

Quantum computing has long been a technology that will be real eventually but isn’t feasible yet. However, in recent years, significant strides have been made to push the state-of-the-art in quantum computing forward. While large-scale quantum computing isn’t quite here yet, the time until it is may be measured in years, rather than in decades.

While quantum computing has many potential use cases, one of the most famous is its ability to break classical cryptographic algorithms. Since many blockchains rely on these types of algorithms, quantum computing seems like an existential threat to these platforms. But is it really?

Quantum computing works fundamentally differently from classical computing. In a classical computer, data is stored and processed in the form of bits, which have values of 0 or 1. This limits the amount of information that can be stored in a bit and the way that algorithms can be written.

Quantum computers, on the other hand, use qubits (“quantum bits”) to store information. Qubits can store values of 0 or 1 or hold both values at the same time due to quantum superposition. As a result, quantum states of N qubits can represent 2^N amplitudes in superposition, which some algorithms can take advantage of. Each qubit doubles the number of calculations performed, unlocking exponential scaling.

This fundamental difference in how the two types of computers work means that quantum computers can be substantially faster than classical ones. Additionally, algorithms can be developed that leverage quantum superposition and entanglement to solve problems in entirely new ways.

One of the most famous quantum algorithms in existence is Shor’s algorithm. Shor’s algorithm transforms the problem of factoring the product of large prime numbers into a related problem that can be solved using quantum superposition. This problem has polynomial complexity, which is substantially better than the subexponential complexity of the best-known factoring algorithm for classical computers.

This reduction in complexity from subexponential to polynomial time is problematic for cryptographic algorithms that are built around the factoring problem. These algorithms assume that multiplying two large prime numbers together has polynomial complexity, while factoring the result has subexponential complexity. This mismatch in complexities makes it possible to set parameters in a way that it’s feasible to find the product of two primes but infeasible to factor the result.

Shor’s algorithm breaks this assumption by reducing the complexity of the factoring problem to polynomial complexity as well. While the complexity of factoring may still be higher than that of multiplication, the fact that they both grow polynomially makes this a problem that can be solved by throwing more money at the problem. If factoring is twice as hard as multiplication, you just need a computer that’s twice as fast or to take twice the time. In contrast, there aren’t enough computers on Earth to factor the numbers used by today’s cryptographic algorithms using classical methods.

Shor’s algorithm and the threat it poses to classical cryptographic algorithms have significant implications for the blockchain. Cryptographic algorithms are the foundation for trust on the blockchain, and many of the blockchains active today use classical cryptographic algorithms based on non-quantum-safe algorithms, such as elliptic-curve-based signature schemes (ECDSA, EdDSA).

Once large-scale quantum computing becomes available, blockchains and the significant value that they store could be the target of attacks exploiting their weak cryptography. Any account that has performed an on-chain transaction in the past has revealed the public key for their account, which Shor’s algorithm can use to reverse-engineer the corresponding private key. As a result, any funds stored on a blockchain not protected by post-quantum cryptography could eventually be vulnerable to “collect now, decrypt later” attacks, where information like public keys is collected and hoarded until quantum computing makes them vulnerable.

However, while this seems like a significant threat to blockchain security, the real risk is limited due to the fact that large-scale quantum computing is unavailable now, but post-quantum algorithms are. Post-quantum replacements for vulnerable classical algorithms have been developed, tested, and standardized already. Blockchains simply need to make the switch from classical algorithms to these newer ones that aren’t vulnerable to quantum computing.

In practice, what this will likely look like is a gradual transition where post-quantum digital signatures are introduced and used alongside classical ones for a time. Once the majority of assets have been moved into accounts that are secured with a quantum-safe signature, then classical algorithms can be phased out.

At the end of the day, one of the riskiest categories may be crypto whose owners have lost their keys and cannot migrate, since those assets cannot be moved to post-quantum-safe accounts. If quantum computers can derive these private keys before classical signatures are abandoned entirely, these coins that were previously lost forever might return to circulation.

Quantum computing is more of a technical challenge than an existential threat to blockchain technology. Post-quantum algorithms are available, meaning that protecting against this risk involves swapping out the classical algorithms and doing the necessary tuning to fix anything that breaks. For example, post-quantum signature schemes require larger signatures and more computation to validate than their classical counterparts. As a result, transactions may become more expensive, forcing a downward shift in gas prices.

For those looking to make the transition to post-quantum security early, it’s possible to do so. Smart contracts and account abstraction both offer the option to specify arbitrary validation logic, including post-quantum signature schemes. This allows protocols and users to secure their assets early, even if platforms haven’t completed their transitions.

When making any major changes to code, especially something at the level of replacing classical cryptography with post-quantum alternatives, security is an essential consideration. Halborn advisory services can help with threat modeling and security by design for quantum transition efforts, as well as performing a comprehensive audit of all smart contract code before it is deployed on-chain. Get in touch.