Cryptography for a World with Quantum Computers
The looming threat of quantum computers means the blockchain community must adopt crypto that can meet the challenge. If quantum computing proves to be as powerful as advertised, most popular blockchains will be vulnerable. Are blockchains doomed? Or can they adapt to this challenge?
By The Praxxis Team, October 15, 2019.
This post is part of a series on quantum computing. Make sure you don’t miss a post from Praxxis: download the xx collective app for your smartphone.
The looming threat of quantum computers means the blockchain community should adopt crypto that can meet the challenge. If quantum computing proves to be as powerful a tool as advertised, most of the encryption currently used by popular blockchains will be vulnerable. Does that mean that blockchains face certain doom, or are quantumresistant alternatives available? How difficult will it be for blockchains to adapt?
The Current Crypto Landscape
Today blockchain platforms are heavily dependent on cryptographic systems – they put the “crypto” in cryptocurrency – that fit in a couple of categories. Proof of Work (PoW) systems such as Bitcoin and Ethereum use hash functions to maintain consensus. And most blockchains use public key cryptography to protect user signatures and wallets.
The strength and security of a crypto system is based on the difficulty of its cryptographic primitive , a mathematical algorithm or function. Hash functions and public key functions are built on “oneway” algorithms that are easy to operate in one direction, but extremely difficult to operate in reverse. Examples include finding prime factors or the discrete logarithm problem, which would take today’s most powerful supercomputers millions of years to reverse.
Quantum computers are dangerous to these crypto systems because their quantum mechanical properties can be used by Shor’s and Grover’s algorithms . Shor’s algorithm in particular makes short work of the oneway algorithms in common use, threatening the public/private keys protecting user signatures and wallets.
QuantumResistant Cryptography
While crypto based on oneway algorithms have been popular for use in blockchains, they are not the only cryptographic systems available. Each of the following systems is believed to be immune to Shor’s algorithm, and while some are vulnerable to Grover’s algorithm, this can be compensated by using larger keys (e.g., by using 256bit keys rather than 128bit keys). The NIST is currently working to establish standards for postquantum cryptography, and has identified 26 candidate systems . Most fit within one of the following categories:

Hashbased cryptography. Drawing on the concept of hashbased signatures created by Leslie Lamport and improved by Ralph Merkle (among others) in the late 1970s, hashbased cryptography includes systems like Merkle trees and Lamport signatures. Traditionally hashbased cryptography has had limited interest because signatures can be used only once, this limitation can be partially overcome by adding many onetime signature keys to a Merkle tree structure.

Codebased cryptography. These systems offer potential quantumresistant publickey encryption. The most prominent codebased system was developed by Robert McEliece, and uses randomization in the encryption process. The chief drawback of codebased cryptography is that quite large public and private keys are required.

Latticebased cryptography. These systems differ from typical publickey cryptography by building on geometric concepts rather than algebraic functions. First developed in the late 1990s, these lattice functions provide cryptographic primitives that aren’t vulnerable to Shor’s Algorithm. There are several latticebased systems, with NTRU the bestknown.

Multivariatequadraticequations cryptography. These systems offer another approach to quantumresistant publickey encryption using cryptographic primitives based on multivariable polynomials. First developed in the late 1980s, the mostresearched system is based on Jacques Patarin’s Hidden Field Equations (HFE), which uses multivariate quadratic equations.

Secretkey cryptography. Used more widely today than the others, secretkey or symmetric key cryptography provides a simpler path to quantum resistance. Systems like Kerberos and the Advanced Encryption Standard (AES) protect against quantum attacks by using large key sizes. The limitation for these systems is finding a way to securely share symmetric keys among trusted members of the system.
Challenges for QuantumResistant Cryptography
While numerous cryptosystems offer quantumresistance, most come with drawbacks that must be dealt with:

Scalability. Many of the above systems achieve quantum resistance by using large keys. These large keys can present a problem at the scale of a large blockchain either by limiting the speed at which new blocks can be created or limiting the number of transactions in each block.

Reusability. Hashbased cryptography in particular makes use of onetime keys. While a large batch of these keys can be generated at the start, blockchains must deal with the question of how to refresh these keys before they run out.

Key Exchange. Symmetric key cryptography has the advantage of already being in wide use today. Once parties share a secret key, the system works well enough. However, the challenge lies in initiating a system by sharing secrets among parties, especially if they are far away from one another or wish to remain anonymous.
Each blockchain will need to grapple with these challenges to implement a quantumresistant cryptographic system, and we expect that many different approaches will be adopted. The Praxxis team has some ideas of our own on how to initiate and maintain a quantumresistant blockchain, and we will begin to describe them in future posts.
An indepth description of postquantum cryptography quickly moves into technical details beyond the scope of this post. For further reading, we recommend PostQuantum Cryptography by Bernstein, Buchmann, and Dahmen.