Introduction

Blockchain public-key infrastructure is built on top of two mathematical problems: integer factorization and discrete logarithm problems, both of which are vulnerable to quantum attacks. This essay describes some of the options and challenges in light of the quantum threat.

Classical vs quantum computers

Classical computers have been around for more than half a century. All of our computing devices, from Raspberry Pi’s to the world's most powerful supercomputers, come from the classical computing paradigm of relying on binary states of information. On the other hand, quantum computers are a rapidly-emerging technology harnessing the laws of quantum mechanics to solve problems which are too difficult to solve on a classical computer. The main difference between classical and quantum computing is the way information is processed. Classical computers store information in binary bits, meaning each bit can only be in one of two states (e.g., on/off, high/low voltage). Quantum computers store information in quantum bits, or qubits, where information is held in a superposition of states with each state having their own amplitudes. Quoting Scott Aaronson, “nature is described not by probabilities (which are always nonnegative), but by numbers called amplitudes that can be positive, negative, or even complex”. Generalizing probability theory to allow minus signs is much of what makes quantum computing special, since summing two non-zero probabilities can lead to a zero probability producing an effect known as quantum interference. Groups of qubits are able to create highly complex, multidimensional spaces giving quantum computers the ability to solve problems that are computationally intractable by their classical counterparts.

Differences between quantum and classical computing

What is security?

There are typically two frameworks used to evaluate the security guarantees of cryptographic systems. These are:

• Computational security - Based on the assumption that adversaries do not possess sufficient computational power to break encryption in a reasonable amount of time.
• Information-theoretic security - Based on mathematical proofs without any assumptions about computational power.

Between computational and information-theoretic security, the latter sets the higher standard by relying on mathematical proofs rather than assumptions about computational power. Unfortunately, information-theoretic security is extremely difficult to implement in practice and most modern cryptographic protocols make assumptions about the available computational power. In order to better understand these assumptions in the computational security framework, let’s turn to computational complexity theory to look at complexity classes.

• P denotes the class of problems that can be solved efficiently on a classical computer.
• BQP denotes the class of problems that can be solved efficiently on a quantum computer.
• NP denotes the class of problems that can be verified (but not necessarily solved) efficiently on a classical computer.

P vs BQP vs NP

These complexity classes have been researched by computer scientists and mathematicians for decades and have helped form the theoretical basis for analyzing the security provided by various cryptographic algorithms. Each class P, BQP, and NP are defined by whether they can be solved or verified efficiently by a classical or quantum computer. Let’s take a look at the significance of these complexity classes with respect to computational security.

Problems in P are known to be solved efficiently by classical computers, so they don’t provide many security benefits from a computational nor information-theoretic perspective. Rather than securing sensitive information using a problem in P, you would want to choose a problem outside of P since there aren't any known classically efficient solutions to those problems. Depending on where in the rest of NP you pick from, you may still need to rely on a computational assumption that there will not be a significant breakthrough in computational efficiency. This is true for the space of BQP where there are known efficient quantum algorithms. So if the problems you pick are outside of P but inside BQP, then there is a very real risk that the chosen security algorithms are not secure in the era of quantum computing. This is where we find ourselves today.

When we selected problems to underpin our digital security decades ago, we selected problems outside P but still within BQP, meaning we were always (and still are) computationally secure under the condition that quantum computers do not exist. This was likely due to the reason that quantum computers weren’t properly conceived when digital security standards were developed. Quantum complexity theory only started around 1992 and Shor’s algorithm arrived in 1994. There was the McEliece asymmetric cryptosystem from 1978 which is based on the hardness of decoding a general linear code which is in the class NP-hard and still thought to be immune to quantum attacks, but at the cost of longer key sizes and ciphertext.

Public-key cryptography in blockchains

Public-key cryptography is based on pairs of related keys (public and private). Generation of these key pairs are based on the intractability of certain mathematical problems such that it’s easy to compute a public key from a private key but not the other way around. This is crucial because a private key represents ownership of a blockchain address and access to the associated funds. Public keys must be able to be broadcasted to the network without making the associated private key vulnerable. This mechanism is critical to the function of the digital signatures associated with each blockchain transaction. Each transaction is signed by a private key in order to verify the legitimacy of the sender. This is done in the following way:

Sign(Transaction, Private Key) -> Signature

Verify(Transaction, Public Key, Signature) -> True/False

This signing mechanism, implemented as a digital signature algorithm, is performed for every transaction in a block. Currently deployed digital signature algorithms are based on the hardness of ECDLP (elliptic curve discrete logarithm problem), which turns out not to be hard for quantum computers. This will be the focus of the next section.

Quantum attack vectors

Attacks on digital signatures

In the previous section, we discussed the role of public-key cryptography elliptic-curves in blockchains. Unfortunately, the security of these systems are based on the hardness of the elliptic curve discrete log problem (ECDLP) for which an efficient quantum algorithm to solve was given by Shor’s algorithm. This algorithm means that a sufficiently large universal quantum computer can efficiently compute the private key associated with a given public key, rendering the public-key cryptosystem completely insecure. Using Shor’s algorithm, one could imagine the following attack on a blockchain network.

In order to send cryptocurrency from an address, the public key associated with that address must be revealed. Once the public key is broadcasted, an adversarial quantum attacker could derive the private key from the public key using Shor’s algorithm. Using the private key, the attacker has the ability to create transactions by sending funds out of that address. In the UTXO model, if an attacker is able to broadcast a new transaction from the stolen address to their own address before the initial transaction is included in a block and made final, the attacker may effectively steal all the funds belonging to the original address. There are also long-lived addresses such as those belong to exchanges which are vulnerable to quantum attacks if they are not immediately drained after receiving customers’ deposits. In an account-based model the attacker is under less time pressure to execute the attack. The initial transaction might not drain all of the funds out of the account, in which case the attacker can continue to drain funds even after the initial transaction posts.

Each transaction is signed by a private key and verified using a public key

Post-quantum cryptography

NIST standardization

The National Institute of Standards and Technology (NIST) is a U.S. Department of Commerce agency which sets the standards for businesses and other organizations to secure sensitive data and protect critical infrastructure. NIST compliance standards must be met by anyone who processes, stores, or transmits sensitive information for the Department of Defense (DoD), General Services Administration (GSA), NASA, and other government agencies, and is largely seen as the de facto standard body to make cryptographic standards for the entire world.

In 2016, NIST initiated a process to solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms. These new cryptography standards will specify additional digital signature and public-key encryption algorithm(s) which are capable of protecting sensitive information well into the foreseeable future, including after the advent of quantum computers.

Earlier this year, NIST officially announced the standardized algorithms from Round 3 of this PQC competition. This is a landmark milestone as government agencies and businesses have been waiting nearly 6 years for a clear direction as to which algorithms are trustworthy.

PQC algorithms for digital signatures

The cryptoalgorithms that can achieve secure digital signatures can be classified into the following categories.

• Lattice based cryptography, for both PKEs and signatures
• Multivariate cryptography, for signatures
• Hash based cryptography, for signatures

Among them, lattice-based cryptography has received a lot of attention in recent years because of its flexibility and reductionist security. The security of a cryptosystem is typically based on an assumption that certain mathematical problems are hard, as well as a reductionist proof that if an attacker can break the said cryptosystem, then we can turn such an attack into an efficient algorithm for solving the underlying hard problem. Several of such hard problems on which a wide variety of lattice-based cryptosystems base their security enjoy a so-called worst-case to average-case reduction. This roughly means that solving a typical instance of the hard problem in a high dimensional lattice is at least as hard as solving the hardest instance in a lower-dimensional lattice. As a result, we can have higher confidence on the security of these lattice-based cryptosystems, as most complexity theoretical results about the hardness of a computational problem only provide guarantees on worst-case scenarios, while we really need stronger evidence that the problem is indeed hard on average.

Hash-based signature schemes represent another design choice in which we minimize the security assumption required in order to achieve a secure digital signature. Hash functions are indispensable in modern cryptography, without which blockchains would not be possible. If we only assume that we have a secure hash function, then we can still construct a digital signature roughly as follows. First, we use one-time hash-based signatures, such as Lamport’s signature or its generalizations such as Winternitz signature, as the building block to actually sign and verify a message. As the name suggests, each public-private key pair of these one-time signature schemes can be used to sign and verify at most once, so we need a way to bundle together many such key pairs in an efficient way to achieve a secure and practical digital signature. Here we use the idea of a Merkle tree to assemble a set of one-time public keys and use the Merkle root as our public key. Every time when we sign with a one-time key pair, we will also need to include the authentication path from this Merkle root to it as part of the signature. Obviously, we need to keep track of which private keys have been used for security purposes, resulting in a stateful hash-based signature, some of which have been standardized, e.g., XMSS in RFC8391.

Multivariate cryptography is another branch of PQC whose security is largely based on the hardness of solving multivariate polynomial equations over a finite field, as well as several related problems such as IP, the problem of determining whether two polynomials are isomorphic. Multivariate cryptosystems tend to have relatively small signature size when used to construct digital signatures, but the public key tends to be large, making them only suitable for a narrow range of applications where there are only a few (well-known) public keys. Unfortunately blockchains are not one of them, as most public keys are only used once for privacy reasons. However, NIST seems to be quite interested in including multivariate cryptography in the basket of PQCs, a decision well justified for the sake of diversification.

In July 2022, NIST selected the following 3 digital signatures to standardize.

• Dilithium, a lattice based digital signature scheme whose security is based on the hardness of finding short vectors in module lattices. It also uses uniform sampling to sample short vectors in a lattice, whose secure implementation tends to be easier and faster than its traditional counterpart based on Gaussian sampling. As a result, Dilithium has a pretty nice balance between public key and signature sizes.
• Falcon, another lattice based digital signature scheme whose security is based on the hardness of the short integer solution (SIS) problem over NTRU lattices. Such an assumption gives Falcon a competitive edge against the more standard lattice-based cryptosystems such as Dilithium when it comes to the combined size of public key and signature. It is also the reason why we believe it is the most suitable digital signature for post-quantum blockchain applications.
• SPHINCS+, a stateless hash-based digital signature scheme. Here the main difference from a stateful hash-based signature such as XMSS is that SPHICS+ uses a very large number of not one-time but few-time signature key pairs and organizes them not into a tree but into a tree of trees. More specifically, the leaves of the parent tree do not sign any messages directly; they only sign the roots of the subtrees, much similar to that of a certificate authority signing a public key (the root of a subtree). Furthermore, these subtrees are generated deterministically, so even if the signer happens to pick the same leaf node of the parent tree, it would be signing the same Merkle root of the subtree. Last but not least, the use of few-time signatures solves the problem of accidentally picking the same message-signing private key at the very bottom of the tree of trees, which happens very rarely anyway.

Consequences of quantum threat

Signature explosion

In order for blockchains to remain secure and viable in the next era of computing, they will have no choice but to transition to post-quantum security standards. Unfortunately this is non-trivial. PQC algorithms are much more expensive than their classical counterparts in terms of size. Even the smallest NIST-approved digital signature algorithm is over 28x larger than the current ECDSA. This is particularly problematic for blockchains where each full node keeps an entire record of all activities on the blockchain. If Bitcoin and Ethereum were to adopt the newly standardized PQC algorithms today, the size of both chains would explode. Even with the most space-efficient NIST PQC signature algorithm, public-keys and digital signatures would consume 21.2x and 24.3x more space in Bitcoin and Ethereum, with the size of their respective ledgers increasing by 2.2x and 2.22x. Other NIST PQC algorithms have even worse tradeoffs between signature/ledger sizes and security. These performance issues have widespread implications, affecting transaction speed, gas prices and the decentralization of the entire network. Upgrading blockchain security isn't as simple as dropping-in a PQC algorithm as a replacement for current algorithms. A solution must be designed to take these consequences into account.

NIST approved digital signature algorithms

Current post-quantum blockchain landscape

Several teams are looking at medium-to-long term solutions for transitioning blockchains to use post-quantum cryptography. Algorand is using the NIST-approved Falcon signatures in their state proofs, which enable the Algorand blockchain to interoperate with other chains. This prevents quantum computers from retroactively forking the chain once the technology is at a sufficiently mature stage. Members of the Ethereum Research team have developed a multi-signature scheme which allows multiple, independent signatures to be compressed into one short aggregated signature allowing for the verification of all the signatures simultaneously. This technique is particularly useful in the scenario where a set of validators need to synchronize on the blocks they sign.

Many thanks to Peter Rhode for his contribution to the section on ‘What is security?’. Thanks to Gavin Brennen for his contribution to ‘Quantum attack vectors’ and to Justin Thaler for his contributions across the article.