On October 23, 2019, Google announced that their quantum processor Sycamore had succeeded in solving a problem in 3 minutes that would have required more than 10,000 years of computation for a supercomputer. It was the first declared case of quantum supremacy.
This technology promises to open up the field of possibilities in many areas. However, it also poses a new risk to modern cryptography, whose security is based on mathematical problems that are difficult to solve. What happens when this calculation difficulty is no longer an obstacle?
In this new series of articles, we explore the potential of quantum computing and analyze its potential impacts on Bitcoin.
What is a quantum computer?
While browsing this article, you are probably using a regular computer or maybe a smartphone. These devices have the ability to perform computational operations, although they have limitations. Indeed, faced with certain complex calculations, the machine would have to run for millions of years before finding a solution. The advantage of a quantum computer is that it can perform certain specific calculations much more quickly than a classical computer.
To achieve this result, the operation of the quantum computer has absolutely nothing to do with the functioning of the classical computer. The traditional computer manipulates bits that can embody two distinct states − 0 or 1 — and that combine to create code and complete tasks. Classical computing is therefore based on the fundamental principles of electricity, while quantum computing is based on the principles of quantum physics.
Instead of processing information with bits, quantum computers use quantum bits, also known as “qubits.” These qubits can be either 0, or 1, or a superposition of 0 and 1. By using this superposition of states with other quantum phenomena such as entanglement and quantum interference, a quantum computer can parallelize calculation tasks, and therefore solve certain problems much more quickly.
The challenge lies in the fact that cryptography is based on mathematical problems that are considered unsolvable by traditional computers. However, it is possible that in the future, these mathematical problems could be solved in an acceptable time by quantum computers, which would break our current cryptographic standards.
What are the risks for cryptography?
To date, there are mainly two quantum algorithms that could threaten some modern cryptographic primitives. These are the algorithms of Shor (1994) and Grover (1996).
The Shor algorithm was designed to decompose whole numbers into their prime factors in polynomial time. This implies that the calculation time required increases in an acceptable manner with the size of the number to be factored. In contrast, the most efficient classical algorithms in this field present a complexity described as “sub-exponential”.
However, some of the most used cryptographic methods in the world are precisely established on this problem of factoring large integers. This is the case with the RSA algorithm for example.
To put it more simply, if traditional computers succeed in breaking the RSA cipher, it is possible to restore the security of the algorithm by increasing the size of the keys used. We are then quiet for a moment, since the complexity increases sub-exponentially with the size of the key. However, with the use of Shor's quantum algorithm, this complexity increases much less quickly, which could ultimately compromise the secure use of encryption methods such as RSA.
This Shor algorithm can be modified in order to also deal with the problem of the discrete logarithm in polynomial time. This is the mathematical problem used in the context of Diffie-Hellman or cryptography on elliptic curves.
The Grover algorithm, on the other hand, can be used to solve unstructured search problems. In other words, it was designed to search for a specific item in an unorganized database, and it does so much faster than a conventional algorithm would. In particular, it can be useful for finding collisions on a hash function.
Grover and Shor are two algorithms that could undermine some modern cryptographic primitives. However, even though they have existed for a long time, it is still impossible to run them on a quantum computer to date.
The reasons for this impossibility are multiple. First of all, we would need to be able to have a quantum computer with a very large number of qubits. Then, these qubits should have a minimal error rate. However, error correction techniques are still under development at the moment. Finally, to perform such complex calculations, qubits must be able to maintain their quantum state long enough. The current times are too short and the information is lost before all the required operations can be carried out.
In the short and medium term, therefore, there does not seem to be a threat to crypto. In any case, this is what emerged from the opinions of experts, as demonstrated by an EvolutionQ survey conducted in 2022 among 40 professionals in the sector.
In this study, they were asked what the probability was that a quantum computer would be able to break a 2,048-bit RSA key in 24 hours, compared to different time horizons starting in the year 2022. Within 5 years, a single expert estimates that there is a greater than 50% chance that the situation described will occur. Within 15 years, more than half of experts consider that the probability exceeds 50%. At 30, almost everyone agrees, and almost a third even believe that there is a 99% chance that an RSA key will be broken.
Credit: globalriskinstitute.org
This survey shows us that in the short and medium term, the threats that quantum computing could pose to cryptography are of little concern to experts. On the other hand, in the long term, they are much more pessimistic.
Conclusion
In this first chapter, you discovered why quantum computing poses a risk to cryptography. The main threats are Shor's and Grover's algorithms. However, we are still a long way from being able to execute them successfully on a machine. This is simply due to the fact that we do not yet have a quantum computer that is sufficiently stable and powerful.
According to experts in this sector, this threat must be taken seriously. However, it is a risk that should not occur for several years or even several decades.
In the second chapter of this series, we will look more specifically at the risks that weigh on the Bitcoin protocol. We will see if quantum computers can have an impact on the invention of Satoshi Nakamoto.
.png)
