How Quantum Computers Break Encryption and What Comes Next

Scientists can secure our infrastructure before quantum computers break encryption

The goal is for a quantum computer to outperform our existing classical computers, achieving what is known as "quantum advantage." However, it is conceivable that quantum computing devices offering this advantage will soon be available. But how will this affect our daily lives?

Making predictions is never easy, but there is a general consensus that cryptography (the science of encrypting and decrypting information) will eventually be transformed by the advent of quantum computers.

It is almost self-evident that privacy is a core issue in our information society: massive amounts of confidential data are exchanged over the internet every day [1]. Meanwhile, the security of these transactions is crucial and depends largely on a single concept: complexity, or more precisely, computational complexity.

Confidential information remains secret because any eavesdropper who wants to read it must solve an incredibly difficult mathematical problem.

In fact, the problems used in cryptography are so complex for our current algorithms and computers that information exchange remains secure for all practical purposes—solving the problem and hacking the protocol would take a ridiculously long time.

The classic example of this approach is the RSA protocol, a public-key cryptosystem whose algorithm was developed in 1977 by Ronald Rivest, Adi Shamir, and Leonard Adleman [2].

The security of the RSA protocol relies on the fact that we do not yet have an efficient algorithm for factoring large numbers—given a large number, the goal is to find two numbers whose product equals the original number.

For example, if the original number is 6, the solution is 2 and 3, since 6 = 2 x 3. Cryptographic protocols are designed so that an adversary, in order to decrypt a message, must factor a very large number (not 6), which is currently impossible.

Therefore, if computing devices are built that can easily crack current cryptography methods, our current privacy paradigm must be rethought. And this is exactly what will happen with quantum computers.

Quantum computers will be able to break RSA

Quantum computers feature an efficient quantum algorithm for factoring [3]. And while classical computers might need the entire age of the universe to solve such a problem, ideal quantum computers could do it in a few hours or even minutes.

This is why cryptographers are developing solutions to replace RSA and achieve quantum security—cryptographic protocols that are secure against an adversary with access to a quantum computer.

Interestingly, to encrypt information in a world equipped with quantum machines, there are two main approaches: post quantum cryptography and quantum key distribution.

The first approach maintains a security paradigm based on complexity: it involves finding mathematical problems that remain extremely difficult for quantum computers and using them to build cryptographic protocols. The idea, again, is that an adversary could hack them, but only after an enormous amount of time. This is exactly why researchers are working hard to develop post quantum cryptography algorithms.

Post quantum cryptography also has a very significant advantage: it is software-based. Therefore, it is inexpensive and, more importantly, its integration with existing infrastructure is straightforward, as it simply requires replacing the previous protocol, say RSA, with a new one.

However, post quantum cryptography also carries a clear risk: our confidence in the "hardness" of the chosen algorithms against quantum computers is limited. It is important to remember here that, strictly speaking, none of the cryptographic protocols have been mathematically proven to be completely secure.

This is due to factoring: we cannot rule out the discovery of an efficient factoring algorithm that would allow a classical computer to break RSA. And while such an event is highly unlikely, the possibility cannot be dismissed.

Harnessing the laws of quantum physics for quantum encryption

The second approach to quantum security is quantum key distribution.

Here, the security of the protocols is no longer based on complexity considerations, but on the laws of quantum physics. Thus, we are talking about quantum physical security [4].

Without going into deep detail, a secret key is distributed using qubits (the equivalent of bits in quantum computers), and the protocol's security stems from the Heisenberg uncertainty principle. This means that any intervention by an eavesdropper is detected because it alters the state of these qubits.

The main advantage of quantum key distribution is that it relies on quantum phenomena that have been verified in many experimental laboratories. However, the primary challenge to its adoption is that it requires new (quantum) hardware, which is quite expensive, and integrating it with existing infrastructure is not easy.

Nevertheless, there are important initiatives underway for quantum key distribution on a European scale.

In any case, the most sound path forward is believed to be a combination of post quantum cryptography and quantum key distribution. If both methods are combined, hackers will face a much harder task, as they will have to overcome both complex computational problems and quantum physical phenomena.