Why Quantum Computing is a Threat to Blockchain Cryptography
Advances in quantum computing threaten many cryptographic systems and the blockchains that rely on them. To respond to this threat, we must understand how cryptography is used today, and recognize why these systems are vulnerable.
By The Praxxis Team, October 3, 2019.
This post is part of a series on quantum computing. To make sure you don’t miss a post from Praxxis, download the xx collective app to receive updates on your smartphone.
Researchers working on quantum computing are making progress. The development of this technology is great news for scientists seeking to understand the quantum mechanical behavior of molecules. However, it poses a threat to many systems of cryptography, as well as the blockchains that rely on them. To understand why this is true, we need to understand cryptography and how it is used by blockchains.
What is Cryptography?
Cryptography is not just for keeping secrets. At a fundamental level, cryptography is about sharing information while protecting against hostile third parties known as adversaries. Cryptography can be deployed to hide information from adversaries, or instead to make the information available to all but prevent adversaries from altering the contents. This latter function is especially important for cryptocurrency systems seeking to demonstrate that no manipulation of a payment ledger has occurred.
Cryptography dates back to ancient times, but in recent decades the field has been transformed by the application of mathematics and computer science. We will focus on the two most common types of cryptography used in the computer age: symmetric key encryption, and asymmetric or public key encryption.
The Major Cryptographic Systems
Systems using symmetric key cryptography use a shared key, which is kept secret, to both encrypt and decrypt information. The chief advantage of symmetric key systems is that they tend to be faster at manipulating data because they are built on simpler underlying algorithms (their cryptographic primitives), and they tend to use keys with shorter lengths. The disadvantage is that the symmetric key must be kept secret, and the act of sharing this key with new parties can be risky. A common example of a symmetric key system is AES (Advanced Encryption Standard).
Systems using (asymmetric) public key cryptography use a pair of keys: a public key used to encrypt information, and a private key used to decrypt. Public key systems are easy to share with new parties, as the public key doesn’t need to be kept secret. In fact, it is common to see journalists publish a public key on their website or social media bio. The disadvantage to public key systems is that they tend to be slower at manipulating data because they are built on more complex cryptographic primitives. Public key systems in common use include RSA (Rivest-Shamir-Adleman) and ECC (Elliptic Curve Cryptography).
In addition, some systems use a hybrid model incorporating both public key and symmetric key cryptography. For example, TLS (Transport Layer Security) uses a public key handshake to establish a symmetric key which is then used for subsequent encrypted communications.
What Makes Cryptography Secure?
The security of a cryptographic system is based on the level of difficulty of a specific mathematical problem, measured by computational hardness or how long it would take a computer to solve the problem. For example, if a problem would take a binary computer one billion years to solve using brute-force methods, we are comfortable assuming that a cryptographic system built on this problem is secure. RSA is computationally difficult because it is built upon a very time-consuming math problem: given a large number, find two primes that are factors of this number. Diffie-Hellman key exchange is computationally difficult because it is built on the time-consuming Discrete Logarithm Problem .
When selecting a cryptographic system, there are multiple trade-offs that involve the hardness behind a specific problem as well as the size of the keys. ECC is gaining wide adoption because it provides a high level of computational hardness and also allows for small key sizes. At the same time, there is some skepticism around ECC because of doubts about how the elliptical curves used in the mathematical problem were chosen. Since the computational hardness of ECC has been presumed to be extremely high, ECC can use 256-bit keys to achieve the same level of security that RSA would need 3,072-bit keys to achieve. But using keys this small leaves little room for error if ECC turns out to be less secure than expected.
How is Cryptography Used in Blockchains?
Cryptography is an important tool for cryptocurrencies and blockchains. Here are three examples of how it is used:
Bitcoin PoW Hash Function. Bitcoin uses a Proof of Work (PoW) consensus algorithm in a blockchain network. For each block in the chain, node servers referred to as “miners” solve a mathematical problem, form the new block and confirm the transactions. The Bitcoin network gives the miners the task of finding a hash function input that satisfies certain output properties. Specifically, the Bitcoin PoW hash function is based on the SHA-256 (Secure Hash Algorithm).
Bitcoin Addresses and Signatures. A Bitcoin address is a virtual location used to receive cryptocurrency payments. Each address has a corresponding signature that can be used to confirm that a payment has been received by the address holder. A Bitcoin address is a 160-bit hash of an Elliptic Curve Digital Signature Algorithm (ECDSA) public key. Using public-key cryptography, the address holder can sign payments with their private key, allowing anyone who knows the public key to verify that the signature is valid.
Elliptic Curve Cryptography. Many blockchains make use of ECC because it offers speed and conjectured security with smaller key sizes. This means that systems could start using smaller keys that offered the same or even greater security. The most popular uses of ECC are the Elliptic Curve Digital Signature Algorithm (ECDSA), the Edwards-curve Digital Signature Algorithm (EdDSA), and Schnorr Signatures (adopted by Bitcoin Cash in May 2019).
Two Quantum Computing Approaches to Break Cryptography
The U.S. National Institute for Standards and Technology (NIST) sets the standards and best practices for a variety of technologies, including cybersecurity and cryptography. Given the importance of the United States to the world economy, these standards are often observed worldwide. Several of the cryptographic systems we described above are among those currently recommended by the NIST. However, the NIST has also cautioned that all of these systems are vulnerable to attacks from an adversary with access to large-scale quantum computers. As a result of this threat, the NIST has initiated a process to solicit, evaluate, and standardize one or more quantum-resistant public key cryptographic algorithms.
There are two major avenues of attack for quantum computing cryptanalysis (the process of breaking cryptographic systems). In both cases, the properties of quantum computers can be used to significantly decrease the computational hardness of cryptographic systems.
Shor’s Algorithm:
In 1994, American mathematician Peter Shor published a paper describing efficient randomized algorithms that could rapidly factor large integers and find discrete logarithms. At the time, Shor built these algorithms using a hypothetical quantum computer. These algorithms significantly reduce the complexity of solving both of these problems. Shor’s algorithm has since been demonstrated by using a five-qubit computer to factor the number 15.
The most popular form of public-key cryptography in current use is RSA, which relies on the difficulty of factoring a large integer, and the Diffie-Hellman Key Exchange, which relies on the Discrete Logarithm Problem. Since Shor introduced a plausible solution to defeat the hardness of both problems, his algorithm represents a real threat to these cryptographic systems.
Grover’s Algorithm:
In 1996, Indian-American computer scientist Lov Grover formalized a quantum algorithm for database search. The problem was formulated as needing to look up a listing in a large phone directory with names arranged in a completely random order. In order to find someone's phone number with a 50% probability, a classical algorithm would need to look at a minimum of half of all the names in the directory. However, Grover discovered that quantum computers can be leveraged to simultaneously examine multiple names, accelerating the lookup process. Grover's algorithm provides a quadratic speedup over classic search algorithms, which is considerable, especially as the phone directory grows. Grover’s algorithm has also been demonstrated, using a three-qubit computer search a small database.
The intended purpose of Grover's algorithm was to optimize a database search. However, it can also be described as an algorithm to invert a function using quantum computing. This represents a threat since many cryptographic primitives rely on the computational hardness of functions that are vulnerable to this algorithm. For example, Grover’s algorithm speeds up the process of inverting hash functions, subverting the security of many systems in current use.
Fortunately, Grover’s algorithm is not as extraordinarily fast as Shor’s algorithm. Many attacks made possible by Grover’s algorithm can be defeated by choosing larger key sizes (e.g., changing from AES-128 to AES-256). Without these protections, Grover’s algorithm could be used to invert hash functions, or even produce fake blocks in several blockchains, which would represent an extremely damaging attack.
How Worried Should We Be About Quantum Computing?
Cryptographic systems play an important role in our daily lives, regardless of the value of one’s cryptocurrency holdings. Cryptography is used throughout the internet, and the hypertext transfer protocol secure (HTTPS) is built on TLS. An adversary with a powerful quantum computer could break the encryption between internet browsers and web servers, putting users’ personal and financial data at risk of identity theft.
Both Shor’s and Grover’s cryptanalysis algorithms have already been demonstrated to work on tiny quantum computers. This leaves two important questions. First, how soon should we expect quantum computers capable of breaking the cryptographic systems in widespread use? Second, is it possible to build cryptographic systems resistant to quantum-capable adversaries?
We will address both these questions in future posts.