Cryptocurrencies and Quantum Computers

Much is being said about the threat quantum computers could pose to cryptocurrencies and cryptography as a whole. The first thing to make clear is that any real threat to cryptography represents something much broader than cryptocurrencies and crypto applications - we would indeed be talking about a major threat to world communications and the Internet as we know it.

How much of it is true and how much is just hype? More importantly, if indeed a threat is present, what is being done about it?

First things first, let’s split out the three major types of cryptography: 

To the best of our knowledge, both hash functions and symmetric cryptography are safe from quantum computers. However, the story is different for asymmetric cryptography. Due to something called Shor’s Algorithm, since 1994 we’ve known that, once a functional large enough quantum computer becomes available, our current asymmetric cryptography standards can be broken in a reasonable time. Here “broken” mostly means finding the private key from its public key counterpart, giving the attacker access to any data encrypted by that key and also the capability of signing messages on behalf of the private key owner, including sending cryptocurrencies.

Created by Peter Shor in 1994, Shor’s algorithm was designed to solve the factorization problem: finding the prime factors of a large number and, considering the existence of a functional quantum computer, doing it in a reasonable time. Factorization is the hard problem that prevents attackers from breaking the widely used RSA asymmetric encryption: it is easy to calculate a large number from two prime factors, but it is hard to calculate the original prime factors from the large number. For the newer ECC family of algorithms, used in most blockchains, the associated mathematical problem is actually the Discrete Log Problem, but suffice to say that Shor’s algorithm can be adapted to solve it as well.

Shor’s algorithm can be summarized as a 6-step process, as it can be seen in the picture below, and it is in fact not that hard to understand. It could be implemented in a classical computer, however in that case the algorithm would run into the same type of computational challenge as other factorization algorithms and take a very long time to complete. 

Shor’s Algorithm

Shor’s algorithm’s clever trick lies in concentrating the computational effort on the fourth step: “Find the period r of a function f(x)”. By leveraging the quantum principle of superposition, the algorithm effectively explores all possible solutions simultaneously by exploring the periodicity (repeatability) of the function, eventually applying a Quantum Fourier Transform (QFT) to exploit the periodic nature and causing incorrect solutions to interfere destructively while amplifying the correct periodicity. This QFT optimization requires periodic functions to work. This dramatically increases the likelihood of observing the desired result when the quantum system is measured. The quantum process is illustrated below.

The Quantum step of Shor’s Algorithm

Since its publication, Shor’s algorithm has been proven in practice by many groups of researchers, for very small numbers. Here is a great video for further explanation on Shor’s algorithm: https://www.youtube.com/watch?v=lvTqbM5Dq4Q

As usual, it depends. If a functional and large-enough quantum computer is available, in theory any exposed public key could be broken, that is, could have its private key revealed. Then the threat would depend on if and how a blockchain is exposing the public keys. 

Let’s take Bitcoin as an example. There are two types of wallet addresses: p2pk, “pay to public key”, and p2pkh, “pay to public key hash”. As we saw, hash functions are safe. However, although p2pkh has been for a long time the default scheme, there are still active p2pk addresses, meaning the public key is exposed in the ledger and vulnerable. Moreover, even p2pkh wallets must reveal their public keys in order to sign a transaction, which could make them vulnerable during the period where the transaction is sitting in the mempool. Any address already used for sending funds would also have revealed their public keys in the ledger.

Things get more complex for crypto use-cases that demand reusable keys, such as proof-of-stake blockchains, DeFi, delegating, and others. In most cases, as soon as users sign a transaction, their public keys are exposed in the ledger, and therefore an open target for a quantum computer. 

In short, no. 

The time it will take for a quantum computer to become available is an educated guess at best, a contentious subject at worst. Some researchers believe we will have functional computers in the next five to ten years, others bet those devices won’t be there in their lifetimes, if at all. If we take a look at these predictions historically, the latter group seems to be winning the argument.

The challenges are certainly enormous: when Google claimed its “quantum supremacy” in 2019, which means they have solved a math problem faster than a classical computer could, they used a computer of 54 qubits. The same company calculated that solving Shor’s algorithm for a 2048-bit RSA key would need around 20 million qubits. Moreover, quantity is not the whole story: error rates and instability are significant obstacles which increase drastically with scale.

On the optimists side, there is an argument that there are plenty of rewards to build a functional device, and hence huge incentives exist that could drive a resourceful player to a breakthrough. Regardless, one thing that is clear is that we will have plenty of time to prepare ourselves against the quantum threat, and we have the same types of smart minds that have made communications secure so far working on the problem.

Post-Quantum cryptography (PQC), also known as Quantum-proof, quantum-safe, or quantum-resistant, is a class of cryptography algorithms that are secure against both classical and quantum computers. They are essentially asymmetric ciphers that also constitute a hard problem for quantum computers to solve. It is important to note that PQC are not quantum algorithms themselves, and therefore can be implemented in classical computers.

PQC algorithms come in many flavors and most are not new science, having resurfaced after the efforts to address the quantum threat. From the many PQC types, lattice-based cryptography has proven to have the best trade-offs and is the main class chosen as the standard by NIST (National Institute of Standards and Technology). The current NIST PQC standard is:

It should be noted that, although NIST has run the process for choosing the PQC standards, it is the broader community of researchers, cryptographers, mathematicians and computer scientists that design, build, test, and scrutinize the algorithms, which ultimately rely on a powerful global consensus to attest for their security.

This question alone could fill an entire paper, but let’s explore the basics, bearing in mind the risk of oversimplification. At the heart of Shor’s algorithm is the ability to find periodicity in a quantum system, which is in turn used to solve mathematical problems like factoring large numbers or computing discrete logarithms. 

As we saw, the clever trick involves mapping the problem in a way to use the Quantum Fourier Transform to extract the periodicity of a function. Importantly, intermediate measurements are not required during the computation, as this would collapse the superposition state prematurely, and one does require a mathematical problem that displays periodicity (repeatability), such as “Find the period r of a function f(x)”. Therefore, a problem that cannot be mapped in such a way cannot use Shor’s algorithm.

This explains why quantum computers are not significantly better at breaking symmetric ciphers like AES. Symmetric encryption security relies on exhaustive key search, and while Grover’s quantum algorithm for example can speed up the search by a factor of two, there is no known solution that can explore Shor’s algorithm “periodicity trick”. Ultimately, symmetric cryptography is more resilient because no known quantum algorithm can fully parallelize the key search or otherwise undermine its security fundamentally. Doubling the key length (e.g., using AES-256 instead of AES-128) is sufficient to mitigate quantum attacks.

Post-quantum cryptography (PQC) therefore works by designing cryptographic schemes based on mathematical problems for which no efficient quantum algorithm is known. These problems—such as lattice-based problems, hash functions, and error-correcting codes—are believed to resist both classical and quantum attacks. Unlike RSA or ECC, they cannot be reduced to a single quantum computation step, such as the period-finding step in Shor’s algorithm. Instead, they are built on inherently more complex structures that remain secure even in the quantum era.

As described previously, the major class of algorithms chosen as the PQC standards are Lattice-based algorithms. A lattice in mathematics is nothing more than an infinite set of points in a coordinate system. The simplest way to visualize an example of a lattice is to imagine an infinite and regular grid of points in a 2 dimensional plane. 

A square lattice

Lattice-based cryptography is therefore a family of algorithms based on hard problems built on top of lattice operations. An example of a lattice problem is to find the point in a lattice that is closest to its origin. Although trivial for a 2-dimensional, fully-built lattice as the above, this problem gets quite complex as we increase the number of dimensions and require the solver to construct the lattice from an origin basis, as seen below.

It is easy to solve lattice problems from basis A above, but the same problems will be hard to solve if you only have basis B

A key characteristic for cryptography is that the same lattice can be defined by different bases. One of the bases could be the “easy” one (basis “A” above), from which it is easy to compute the lattice, and the other the “hard” one (basis “B” above). Calculating a specific point, let’s say the point closest to the origin, is trivial if you have the easy basis, but hard if you only have the hard basis, which creates an ideal scenario for asymmetric cryptography, where the public key is related to the hard basis and the private key is related to the easy basis. Moreover, lattice operations require the type of computation that cannot be optimized by quantum computers and cannot be solved by Shor’s algorithm.

First and foremost, education is important, so people involved understand the security capabilities and limitations of cryptography, including how we will eventually protect against quantum-based attacks. Most importantly, there is no reason for panic or discredit: cryptographers and the broader security community are dealing with the threat as they have always done in the past.

Now that the PQC standards have been defined, we will eventually need to upgrade our systems and fork blockchains to change from ECC to PQC, while users upgrade their wallets. This could have broader implications for users, such as changing hardware wallets or recovery phrases, or accepting a lower performance standard. As long as we prepare ourselves in advance with proper knowledge and tools, the transition can be smooth. Many companies have already started running real-life tests with PQC.

At Coinbase, we are actively looking into PQC for crypto, diving into the subject in an early stage, educating the community, participating in cryptography research, and trying some implementations ourselves. This way we can guarantee the security of our users and of the broader community, while also enabling a smooth transition when the time of post-quantum cryptography comes. As we have pointed out, the power of community consensus is what allows crypto to succeed, and we will make sure we play our part in it.