No one knows when that will be, but the quantum machines for crypto-encryption will come. Here you will learn how researchers use quantum mechanics to crack long integers in asymmetric cryptography. […]
Quantum informatics is still moving in a nebulous area between practical application and theoretical speculation, but it is getting closer and closer to the real [weiterführende Artikel in Englisch] Application. One of the most interesting use cases for quantum computers is modern Internet cryptography.
Quantum computers and Qubits
The name quantum computer is due to the fact that it relies on the properties of subatomic particles subject to laws that seem strange to us who are rooted in the macroworld. In particular, quantum computers use qubits (quantum bits) instead of the binary digits (bits) that we know from conventional computer systems.
Qubits are probabilistic by nature, while bits are deterministic. A bit is ultimately a physical switch – albeit a very small one, measured in a handful of nanometers. Bits are binary: either on or off, true or false, 0 or 1.
Not so with qubits.
The physical basis of a qubit can be numerous phenomena, such as the point of rotation of an electron or the polarization of photons. This is a fascinating topic: the realm of linear equations that bridge the gap between imagination and reality. Quantum mechanics is considered an interpretation of an underlying reality rather than a description, and it involves a high computational effort.
The state of a qubit is described as a linear superposition of the two possible states. Once observed, the state is resolved into true or false. However, the same input does not necessarily lead to the same output, and the unobserved state can only be described using probability assumptions.
From the point of view of classical physics, it is even more amazing that qubits in a quantum computer can assume several states at the same time. When a computer samples a qubit for its state, it resolves into a single either-or (known as a collapse of the wave function).
Quantum computing in cryptography
All this is quite interesting from a scientific and philosophical point of view. The functioning of quantum computers, for example, proves the effect of observations on particles. But here we are talking about the practical aspects of the increasing capacity of quantum computers for our daily life. In the coming years, the most profound effects will probably be felt in cryptography.
The most famous path from quantum computing to cryptography is a theoretical breakthrough from 1994: the Shor algorithm. Theoretically, this algorithm showed that a quantum Turing machine is capable of efficiently solving a class of problems that were unsolvable with conventional computers: the factorization of large integers.
If you are familiar with the algorithms of asymmetric cryptosystems such as Diffie-Hellman and RSA, you know that they are based on the problematic of solving factors for large numbers. But what happens when quantum computing solves this task?
Cracking Large Integers with Quantum Mechanics
Shor’s algorithm and a handful of other algorithms use quantum mechanics to crack the one-way functions that form the core of asymmetric cryptography. Adiabatic quantum computation has also been used to attack factorization.
The algorithms of Shor and others are based on the ability of the quantum computer to occupy a variety of states thanks to the qubits. These qubits are then sampled (causing their state to collapse) in a way that allows for a high degree of probability in the sampling. In essence, we give the question “What are the factors for a given number?” on to the mysterious world of the invisible, in which the particle properties can exist in several states. Then we query these properties to find the most likely answer. (Yes, this actually works.)
The largest number factorized so far using Shor’s algorithm is 21. Adiabatic quantum computation has successfully factorized 143.
These algorithms are sophisticated and impressive, but so far their numbers are rather modest. The current standard for RSA is 2048 bits, that’s 617 digits! However, when attacking the number 143, the researchers unknowingly discovered an approach that, at least in theory, allows even larger numbers. An example is 56,153, which is still a relatively small number compared to what would be required to compromise real cryptosystems. It also depends on a reductive trick, which can not be used for all numbers.
The threat to the Web security infrastructure
What we currently know is that the fundamental aspects of the quantum attack on asymmetric algorithms are being refined. How fast will the technology advance to the point where it can approach significantly larger numbers?
Interestingly, the symmetric algorithms we use every day (like AES) are not particularly susceptible to quantum algorithms. Grover’s algorithm is the one that finds application. Even in theory, it is not able to shorten the time required for an attack on these algorithms much further than classical algorithms, provided that 256-bit keys are used.
However, the majority of symmetrically secured communication establishes its keys via an asymmetric exchange. Therefore, most web traffic today is vulnerable to advanced quantum computer attacks. If an attacker can find out the key set at the beginning of an interaction, no matter how good symmetric encryption is, it is of no use.
So the threat to the web security infrastructure is real. Let’s think for a moment about the dynamics that are at play here. The first thing we need to take into account is the economic aspects and access. At the moment, only companies that are swimming in money can afford to tinker with such things. IBM, Google and researchers in China are vying for leadership in developing viable systems, as are a number of universities. Behind the scenes, government agencies such as the US National Security Agency are certainly not idle. The NSA even has its own opinion on the topic of public cryptography and quantum computers.
Future-oriented protection against quantum computers
Small players are unlikely to achieve quantum computing capabilities sufficient to attack modern asymmetric keys until long after large institutions have done so. This means that we are in a long period of time in which the security infrastructure can evolve in response to the dynamics of quantum computing.
No one knows when there will really be crypto-compatible quantum computers, but it seems likely that it will come to this. Two measures to answer this question are the number of qubits in a system and the longevity of these qubits.
Qubits are subject to the so-called decoherence. Entropy is constantly in the process of destroying the delicate ensembles of electrons and photons. The problem is that both the number and the lifetime of qubits are difficult to quantify. How many qubits are required for a convenient, reproducible attack on an RSA-2048 key? Some say dozens, others say millions. How much coherence is required? Some say hundreds of nanoseconds, some say minutes.
And all this can be overturned by such techniques as the already mentioned tricky use of pre-processing algorithms. Who knows which brilliant student is currently thinking up a new approach. The people who calculated 143 on a quantum machine did not realize until two years later that they had also cracked 56,153.
All roads lead to a post-quantum world, and many people are already working intensively on it. The US National Institute of Standards and Technology is currently holding competitions to develop quantum-resistant algorithms. Some of these efforts are already yielding results.
Ultimately, we can say that the quantum threat to cryptography is real, and on the basis of more and more results from practice. But at the moment it is more than compensated by opposing forces. Perhaps at some point we will have to say goodbye to some of our beloved algorithms, but new ones will take their place.
It will be an interesting dance that we will observe in the next decade.
*Matthew Tyson is the co-founder of the Dark Horse Group, Inc. He believes in technology where people come first. When he’s not playing the guitar, Matt explores the hinterland and the philosophical realms. He has been writing for JavaWorld since 2007.