Quantum Computers and Cryptocurrencies

Community Submission - Author: John Ma

Introduction

Quantum computers are powerful machines that can solve complex equations much more quickly than regular computers. Some experts estimate that they could crack encryption that would take the fastest computers of today thousands of years in mere minutes. As a result, most of today’s digital security infrastructure could be at risk — including the cryptography underlying Bitcoin and cryptocurrencies.

This article will give an introduction to how quantum computers are different from regular computers and what risks they pose to cryptocurrencies and digital infrastructure.

Asymmetric cryptography and Internet security

Asymmetric cryptography (also known as public-key cryptography) is a critical component of the cryptocurrency ecosystem and most Internet infrastructure. It relies on a key pair to encrypt and decrypt information - namely, a public key to encrypt and a private key to decrypt. In contrast, symmetric key cryptography only uses one key to encrypt and decrypt data.

A public key can be freely shared and used to encrypt information, which can then only be decrypted by the corresponding private key. This ensures that only the intended recipient can access the encrypted information.

One of the main advantages of asymmetric cryptography is the ability to exchange information without needing to share a common key across an untrusted channel. Without this crucial ability, basic information security would have been impossible on the Internet. It is difficult to imagine online banking, for example, without the ability to safely encrypt information between otherwise untrusted parties.

If you’d like to read more on the subject, check out Symmetric vs. Asymmetric Encryption.

Some of the security of asymmetric cryptography relies on the assumption that the algorithm generating the key pair makes it incredibly difficult to calculate the private key from the public key, while it is simple to calculate the public key from the private key. In mathematics, this is called a trapdoor function, because it is easy to calculate in one direction but difficult in the other. 

Currently, most modern algorithms used to generate the key pair are based on known mathematical trapdoor functions. These trapdoor functions are not known to be solvable in a timeframe that would be feasible for any existing computer. It would take immense amounts of time for even the most powerful of machines to perform these computations. 

However, this might soon change with the development of new computing systems called quantum computers. To understand why quantum computers are so powerful, let’s examine how regular computers work first.  

Classical computers

Computers that we know today can be called classical computers. This means that computations are done in a sequential order - a computational task is executed, and then another one can be started. This is due to the fact that the memory in a classical computer must obey the laws of physics and can only have a state of either 0 or 1 (off or on).

Various hardware and software methods exist that allow computers to break up complex computations into smaller chunks to gain some efficiency. However, the basis remains the same. A computational task must be completed before another one can be started.

Let’s consider the following example, where a computer must guess a 4-bit key. Each of the 4 bits can either be a 0 or a 1. There are 16 possible combinations, as shown in the table:

A classical computer needs to guess each combination separately, one at a time. Imagine having a lock and 16 keys on a keychain. Each of the 16 keys has to be tried separately. If the first one does not open the lock, the next one can be tried, then the next one, and so on until the right key opens the lock.

However, as the key length grows, the number of possible combinations grows exponentially. In the example above, adding an extra bit to increase the key length to 5 bits would result in 32 possible combinations. Increasing it to 6 bits would result in 64 possible combinations. At 256 bits, the number of possible combinations is close to the estimated number of atoms in the observable universe.

In contrast, computational processing speed only grows linearly. Doubling the processing speed of a computer results in only a doubling of the number of guesses that can be made in a given time. Exponential growth far outstrips any linear progress on the guessing side.

It is estimated that it would take millennia for a classical computing system to guess a 55-bit key. For reference, the minimum recommended size for a seed used in Bitcoin is 128 bits, with many wallet implementations using 256 bits.

It would appear that classical computing is not a threat to the asymmetric encryption used by cryptocurrencies and Internet infrastructure.

Quantum computers

There is a class of computers currently in their very early stages of development for which these classes of problems would be trivial to solve - quantum computers. Quantum computers are based on fundamental principles described in the theory of quantum mechanics, which is concerned with how subatomic particles behave.

In classical computers, a bit is used to represent information, and a bit can have a state of either 0 or 1. Quantum computers work with quantum bits or qubits. A qubit is the basic unit of information in a quantum computer. Just like a bit, a qubit can have a state of 0 or 1. However, thanks to the peculiarity of quantum mechanical phenomena, the state of a qubit can also be both 0 and 1 at the same time.

This has spurred research and development into the field of quantum computing, with both universities and private companies investing time and money into exploring this exciting new field. Tackling the abstract theory and practical engineering problems that this field presents is on the cutting edge of human technological achievement.

Unfortunately, a side effect of these quantum computers would be that the algorithms that form the basis of asymmetric cryptography would become trivial to solve, fundamentally breaking the systems that rely on them.

Let’s consider the example of cracking the 4-bit key again. A 4-qubit computer would theoretically be able to take all 16 states (combinations) at once, in a single computational task. The probability of finding the correct key would be 100% in the time that it would take for it to perform this computation.

Quantum-resistant cryptography

The emergence of quantum computing technology could undermine the cryptography that underlies most of our modern digital infrastructure, including cryptocurrencies.

This would put the security, operations, and communications of the entire world at risk, from governments and multinational corporations to the individual user. It is no surprise that a considerable amount of research is being directed at investigating and developing countermeasures to the technology. Cryptographic algorithms that are assumed to be secure against the threat of quantum computers are known as quantum-resistant algorithms.

On a basic level, it appears that the risk associated with quantum computers could be mitigated with symmetric key cryptography through a simple increase in key length. This field of cryptography was sidelined by asymmetric key cryptography due to the issues arising from sharing a common secret key across an open channel. However, it may reemerge as quantum computing develops.

The problem of securely sharing a common key across an open channel might also find its solution itself in quantum cryptography. Advances are being made to develop countermeasures against eavesdropping. Eavesdroppers on a shared channel could be detected using the same principles that are required for the development of quantum computers. This would make it possible to know if a shared symmetric key had been previously read or tampered with by a third party.

There are other avenues of research being investigated to defeat possible quantum-based attacks. These can involve basic techniques such as hashing to create large message sizes or other methods such as lattice-based cryptography. All of this research aims to create types of encryption that quantum computers would find difficult to crack.

Quantum computers and Bitcoin mining

Bitcoin mining also uses cryptography. The miners are competing to solve a cryptographic puzzle in exchange for the block reward. If a single miner would have access to a quantum computer, it may gain dominance over the network. This would reduce the decentralization of the network and potentially expose it to a 51% attack. 

However, according to some experts, this isn’t an immediate threat. Application-Specific Integrated Circuits (ASICs) can reduce the effectiveness of such an attack — at least for the foreseeable future. Also, if multiple miners have access to a quantum computer, the risk of such an attack is significantly reduced.

Closing thoughts

The development of quantum computing and the resulting threat to current implementations of asymmetric encryption seems to be only a matter of time. However, it isn’t a problem of immediate concern - there are gigantic theoretical and engineering hurdles to overcome before it is fully realized.

Due to the immense stakes involved in information security, it is reasonable to start laying the groundwork against a future attack vector. Thankfully, there is a great deal of research being conducted into potential solutions that could be deployed to existing systems. These solutions, in theory, would future-proof our critical infrastructure against the threat of quantum computers.

Quantum-resistant standards could be distributed to the wider public in the same way that end-to-end encryption was rolled out through well-known browsers and messaging applications. Once these standards are finalized, the cryptocurrency ecosystem could integrate the strongest possible defense against these attack vectors with relative ease.