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 quantum-resistant 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 “one-way” 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 one-way algorithms in common use, threatening the public/private keys protecting user signatures and wallets.
Quantum-Resistant Cryptography
While crypto based on one-way 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 256-bit keys rather than 128-bit keys). The NIST is currently working to establish standards for post-quantum cryptography, and has identified 26 candidate systems . Most fit within one of the following categories:
-
Hash-based cryptography. Drawing on the concept of hash-based signatures created by Leslie Lamport and improved by Ralph Merkle (among others) in the late 1970s, hash-based cryptography includes systems like Merkle trees and Lamport signatures. Traditionally hash-based cryptography has had limited interest because signatures can be used only once, this limitation can be partially overcome by adding many one-time signature keys to a Merkle tree structure.
-
Code-based cryptography. These systems offer potential quantum-resistant public-key encryption. The most prominent code-based system was developed by Robert McEliece, and uses randomization in the encryption process. The chief drawback of code-based cryptography is that quite large public and private keys are required.
-
Lattice-based cryptography. These systems differ from typical public-key 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 lattice-based systems, with NTRU the best-known.
-
Multivariate-quadratic-equations cryptography. These systems offer another approach to quantum-resistant public-key encryption using cryptographic primitives based on multi-variable polynomials. First developed in the late 1980s, the most-researched system is based on Jacques Patarin’s Hidden Field Equations (HFE), which uses multivariate quadratic equations.
-
Secret-key cryptography. Used more widely today than the others, secret-key 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 Quantum-Resistant Cryptography
While numerous cryptosystems offer quantum-resistance, 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. Hash-based cryptography in particular makes use of one-time 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 quantum-resistant 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 quantum-resistant blockchain, and we will begin to describe them in future posts.
An in-depth description of post-quantum cryptography quickly moves into technical details beyond the scope of this post. For further reading, we recommend Post-Quantum Cryptography by Bernstein, Buchmann, and Dahmen.