Quantum threat of blockchain and cryptographic systems

Introduction

The possible risk of quantum computing is considered to be a bigger threat every day. Recently, even the Bank for International Settlements published an interesting report for analyzing possible quantum risks of a classical financial infrastructure [1]. Considering the rise of blockchain-based systems this threat might even be bigger. Afterall, these systems are pretty complex and contain many different parts with different cryptographic primitives. Additionally, there are an increasing number of mission critical applications implemented on different blockchain platforms, like stablecoins, CBDCs, deposit token or identity solutions. 

This two-part series delves into quantum threats to cryptography and blockchain systems. It also proposes a quantum risks assessment framework for different distributed ledger-based platforms to systematically evaluate quantum vulnerabilities of different DLT platforms. The framework assesses possibilities and impacts of different quantum computing attacks and proposes steps for mitigating risk. It has relatively easy integration possibilities with classical technology and  risk management approaches. 

Quantum world and quantum computing

Quantum computing is one of the possible emerging technologies that can disrupt many existing industries. The technology is based on quantum physical and mechanical aspects of photons, electrons and other particles, exploiting the dual wave-particle characteristics in the computation. On a deep physical level, things work pretty differently than we would intuitively expect. To demonstrate the counterintuitive nature of the quantum world, one of the most famous experiments is the double slit experiment (Figure 1). In this experiment photons or other atomic particles are shot from an electron beam or laser gun to a plate by two parallel slits. Behind the plate there is a screen that observes the hit of individual photons. If our laser beam is sensitive enough and we can practically shoot the photons on a one by one basis and measure them on the screen, we will experience the photons hitting the screen on a one by one basis. If, however, we shoot many photons and we measure only the aggregated appearance on the screen, we will get an interfering wave function. Things can get even weirder if we make measurements directly at the double slits as well.     

There are many competing ideas and theories trying to explain the double slit and similar experiments, including heavy mathematics and complex physical explanations. Without covering these theories in detail, we can say that if we are looking at a small enough object, like a particle, a neuron or a photon, it sometimes behaves as an object and sometimes as a wave or rather a probability wave. 

Figure 1. Dual-slit experiment

source wikipedia https://en.wikipedia.org/wiki/Double-slit_experiment 

Although the theory behind it is still being investigated, computer scientists try to build computational models and actual computers based on this incomplete and sometimes inconsistent conceptual background. The basic building block is the so-called qubit (quantum bit). Similar toclassical computers that use bits as a basic building block to hide the complexity of the physical hardware, like transistors or analogue circuits, quantum computers use qubits. A normal bit can have two values, either 0 or 1, a quantum bit can have both 0 and 1 as well as all the possible values between 0 and 1 as well (Figure 2). The idea of having 0, 1 and all the possible values in between is called a superposition. It practically models the wave characteristics of the underlying physical particle. A qubit that is in a superposition can be measured as well. If it is measured, a certain value will be measured that is either 0 or 1. At measurement, the wave characteristics of the particle collapses and the object kind description will dominate, causing the measured qubit to have a similar characteristics as a normal bit. Real strength of qubits compared to classical bits is manifested if we are able to use several qubits parallelly. Having n pieces of qubits in superposition states can practically mean that there can be two to the power of n computational state considered in the same time. It can bring in certain situations an exponential faster computational speed than classical computers.     

Figure 2. Quantum bit, qubit

source wikipedia https://en.wikipedia.org/wiki/Qubit 

Even if quantum bits can be much faster than classical computers, building real life or sometimes even theoretical quantum algorithms can be pretty challenging. One way of building quantum algorithms is to capitalize on additional physical elements of wave particle duality, like entanglement or interference. Entanglement means connection between two qubits, in a sense that their state is not completely independent from each other. Although both qubits are in superposition, meaning that they are in the state of zero and one and all the possible values in between, if we measure a qubit it will determine the measured value of the other qubit as well. The exact physical explanation of entanglement is still not fully underwood. However, it does not prevent computer scientists from using a kind of deterministic connection between qubits to build quantum algorithms. One way of implementing a quantum algorithm is to use atomic deterministic connection between qubits as building blocks, called quantum gates. A quantum gate transforms the superpositioned state of a qubit or several different qubits into something else, playing  a similar role to classical gates in classical computers and digital circuits. Quantum gates can be combined as well into more complex transformations, called quantum circuits.   

As a demonstration, Figure 3 contains a very simple quantum circuit. A quantum circuit contains qubits for quantum computation and classical bits for evaluating the result of the quantum computation. It usually starts by quantum bits in a zero state that are put into superposition with the help of a special circuit, called the Hadamard gate. Calculation is realized by applying different quantum gates to the superpositioned qubits. The algorithm ends by making a measurement for the qubits and storing the result in classical bits. 

Figure 3. A simple quantum circuit 

Source, wikipedia, https://en.wikipedia.org/wiki/Quantum_circuit 

With the help of quantum circuits, there is a way of implementing quantum algorithms and analyzing the possible impact of quantum computers, even if the necessary hardware is still not or only partially available. One possible application of quantum computers is to calculate the so-called computationally difficult problems in a more efficient way. Important examples are solving prime factorization or elliptic curve multiplication in a more efficient way. Due to the massive parallelization of qubits, these problems can be theoretically solved exponentially faster with a quantum computer than with classical ones. It causes serious concerns for cryptography practitioners as most of our currently used cryptographic protocols, like secure and private data exchange, use one of the previously mentioned mathematical problems. 

It is important to point out that quantum computers can have different computational models than quantum circuits and the most interesting application area is not necessarily breaking cryptographic protocols. Quantum computers are expected to be better in solving different optimization and simulation problems than competing with classical computers in running traditional algorithms faster. This direction is called Quantum Annealing (QA), which is an optimization process for finding the global minimum of a given objective function over a given set of candidate solutions (candidate states) [2]. Applications of such optimization range from running financial market simulations, via designing better medicines, to weather forecasting or modeling climate change. From a blockchain perspective, quantum algorithms having the possibility of cracking cryptographic primitives play the most important role. 

Realizing a quantum computer is far from being trivial at the moment. It requires extreme physical conditions, like temperature near absolute zero. Another problem is that most of the nowadays quantum computers are not too stable. It means, on the one hand, that the realized qubits have a very high error probability and realizing efficient quantum error correction is still challenging. On the other hand, most systems get decoherent pretty fast due to physical limits, so only small quantum programs can be planned to run. Quantum computers are definitely not science fiction; there are already quantum hardwares running at least up to 1000 qubits. There are even quantum cloud platforms where even everyday users can run programs on quantum computers as jobs with the help of cloud infrastructure [3]. Although the current size of current computers are not really big enough for solving real life problems, due to the exponential development in the field this can radically change in a decade.  

Quantum computing and cryptography

Quantum computing might have a lot of interesting applications. Considering blockchain applications and challenges, however, the most important area is in relation with cryptography. As we mentioned above, one possible threat to cryptography is the speed or rather parallelization possibility of quantum computers. They are capable of solving specific hard mathematical problems much faster than classical computers. These hard mathematical problems are often the basis for cryptographic primitives, causing a serious cybersecurity threat. From a practical point of view there are two quantum algorithms that are considered to be critical for any applications containing cryptographic primitives:

• Shor’s algorithm is a quantum algorithm finding the prime factors of an integer in polynomial time [4]. Advanced usesages of the algorithm are able to break elliptic curve factorization as well. The problem is that some of the most important cryptographic protocols are based on prime or elliptic curve factorizations. Most criticals are RSA and ECC cryptography, which are the basis of public - private key cryptography, digital signatures, key exchange protocols heavily used in all nowadays protocols like in TLS. The real problem is that these protocols are exponential (or believed to be exponential).  However, with the help of Shor’s algorithm, they can be solved in polynomial time making practically these cryptographic techniques useless. Although current quantum computers are not advanced enough to break currently used, like 2048 bit RSA crypto systems, the quantum threat is considered to be real. As most secure communication channels use the previously mentioned problems, there is a possibility to store secret communication now, and decrypt it in like 10 years as soon as strong enough quantum computers will be available. This is the so-called harvest now, decrypt later attack. For some of the mission critical data, like sensible financial information that should be kept private for a longer timeframe, this can pose a serious threat.   
•  
• Grover’s algorithm is a quantum algorithm for searching in unstructured data. Instead of polynomial time with a classical computer, the search with the Grover’s algorithm takes square root steps, reaching a quadratic speedup [5]. Grover’s algorithm can be used to crack several well-known cryptography primitives as well, like symmetric encryption (like AES) or cryptographic hash functions (like SHA-256). The impact of this algorithm is not so critical compared to the Shor’s algorithm, as there is just a polynomial, quadratic speed-up and not exponential. As a consequence, most of the affected cryptographic protocols and primitives can be improved with increased key-size to be resistant to Grover’s algorithm. While , there is no need to invent brand new cryptographic algorithms here, changing the key size of a symmetric cipher or hash function on a live blockchain system might be challenging. It might require serious planning, preparation and testing.   

To prevent vulnerabilities of cryptography against quantum attacks, there are two possible directions that are heavily investigated:

• -Post-quantum cryptography tries to invent new cryptographic technologies that can be run on classical computers but are vulnerable to quantum attacks, like the Shor’s or Grover’s algorithm. They are based on difficult mathematical problems, different from prime or elliptic curve factorizations, that are hard to solve even by quantum computers. 

• Quantum cryptography  consists of brand new cryptographic protocols that can be implemented and executed only by quantum computers. 

Independently, if we speak of quantum or post-quantum protocols, inventing and standardizing a brand new cryptographic primitives is always a long-running and challenging process that requires a lot of contribution among the top cryptographers of the world. To speed-up standardization and the invention of stable and usable post-quantum algorithms, NIST (National Institute of Standards and Technology) created a standardization challenge. In this challenge, several post-quantum algorithms in several rounds have been competing with each other to become the standardized post-quantum cryptography of the future  [6].

The NIST post-quantum cryptography challenge started back in 2010 to help the world to be ready for quantum attacks against cryptography. In 2016 a global competition started where individual independent teams from around the globe could come out with brand new quantum resistant algorithms and let them evaluate. The purpose of this competition was to find and standardize the next series of cryptographic algorithms that are resistant both to quantum and to traditional attacks as well. The competition has been taking place for several years, containing multiple rounds of submission and evaluation. The proposed algorithms were evaluated based on different criteria, like performance, complexness, quantum and classical vulnerabilities. From the originally proposed 69 candidates there are 7 finalists and 8 alternative solutions selected. The candidate algorithms are based on hard underlying mathematical problems that are believed to be hard to crack even by quantum computers. These mathematical problems are the following [7]:

• Lattice-based cryptography: built on the mathematical concept of lattice, where lattice is a mathematical structure of abstract algebra. 
• Hash-based cryptography: creates digital signature algorithms based on cryptographic hash functions, exploiting the idea that hash function are more resistant to quantum attacks (see Grover’s algorithm)
• Multivariate cryptography: built on multivariate polynomials over a finite field.
• Code-based cryptography: based on error-correction codes and exploits the difficulty of decoding a linear error-correcting code.
• Isogeny-based cryptography:  based on walks in a supersingular isogeny graph.

The challenge is nearing its conclusion with the announcement of the first three finalists and standardized post-quantum cryptography standards [8]. The new algorithms are based on lattice-based and hash-based cryptography. Having the first official standards is an important milestone, but creating new implementations and replacing old cryptography with the newly defined post-quantum counterparts might take at least a decade from now. The first three standardized post quantum cryptographic algorithms are the followings: 

• FIPS 203: it is a key encryption / encapsulation (KEM) mechanism based on lattice based cryptography. The standard is based on the CRYSTALS-Kyber algorithm. 
• FIPS 204: it is the primary standard for digital signatures, based on lattice based cryptography and on the CRYSTALS-Dilithium algorithm. 
• FIPS 205: it is also a digital signature algorithm based on hash based cryptography and on the Sphincs+ algorithm. 

Besides post-quantum cryptography, a very interesting initiative is quantum cryptography. Quantum cryptography means cryptographic algorithms running on quantum computers or based on quantum physics. Although the field seems to be a little bit speculative, because actually there are still no efficient enough quantum computers running real quantum algorithms, there are some real-life applications. These applications rather focus on different quantum physical effects and are not necessarily based on structured quantum computers with qubits,  quantum gates or circuits. 

One of the interesting and very useful fields is random number generation. Using a good, cryptographically secure random number is highly critical, for example, in key generation in every system containing cryptographic components, including TLS key or private keys for identity (like private keys of Bitcoin addresses). If the key is not generated with a high enough entropy, it can be guessed by a hacker and the stored bitcoin can be stolen. One such example is the mindwallet, in which a hash value of a secret passphrase was used as a private key. It turned out that it is insecure, simply because a passphrase chosen by a human does not have enough entropy. One novel approach is to use a device based on quantum devices to guarantee that the generated random number is a real random (QRNG quantum random number generation). Real randomness is guaranteed by quantum physics. Such devices are already available for a reasonable price.

Another practical quantum application is the so-called quantum key distribution (QKD). It is a key distribution protocol between two parties to come to an agreement of a common secret. It is based on quantum mechanical properties of a laser beam that makes it impossible for an eavesdropper to find out the common secret. The quantum physical mechanism behind is called the no-cloning theorem [8]. Although QKD protocols exist in real life, they are not yet practical, scalable or economically feasible. Nonetheless, there are existing initiatives and elaborated protocols, such as the BB84 protocol.   

Both quantum cryptography and post-quantum cryptography are strongly emerging fields. We will surely see a lot of theoretical and practical advancements in both fields in the coming decades.  

Glossary

References

[1] Project Leap: quantum-proofing the financial system, BIS Innovation Hub, 2024

[2] Atanu Rajak, Sei Suzuki, Amit Dutta, Bikas K. Chakrabarti, Quantum Annealing: An Overview

[3] IBM Quantum Platform 

[4] Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, 

[5] Grover’s algorithm, wikipedia, Lov K. Grover, A fast quantum mechanical algorithm for database

[6] NIST, Post-Quantum Cryptography project

[7] Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen, Post-Quantum Cryptography, Springer 2009

[8] NIST Releases First 3 Finalized Post-Quantum Encryption Standards