How to prevent quantum computers from threatening the entire cybersecurity infrastructure

13, 53 and 433. This is the scale of quantum computers in terms of qubits, or qubits, which have grown significantly over the past few years due to significant public and private investments and initiatives. Obviously, it's not just a matter of quantity: the quality of the prepared qubits is just as important as their quantity, and quantum computers want to beat our existing classical computers to gain what is known as "quantum advantage." However, it is conceivable that quantum computing devices that offer this advantage will soon be available. How will this affect our daily lives?

Making predictions is never easy, but there is consensus that the advent of quantum computers will change cryptography. Privacy is a key issue in our information society, and it's almost trivial to say: every day, vast amounts of confidential data are exchanged over the Internet. The security of these transactions is paramount and depends mainly on one concept: complexity, or more accurately, computational complexity. Confidential information remains secret because any eavesdropper who wants to read it needs to solve an extremely complex mathematical problem.

In fact, the problems used for cryptography are so complex for our current algorithms and computers that the exchange of information is secure for any practical purpose — solving the problem and then breaking the protocol would take ridiculous years. The most typical example of this approach is the RSA protocol (for its inventors Ron Rivest, Adi Shamir, and Leonard Adleman), which today protects our information transmissions.

The security of the RSA protocol is based on the fact that we don't yet have any effective algorithm for factoring large numbers – given a large number, the goal is to find two numbers whose product is equal to the initial number. For example, if the initial number is 6, the solution is 2 and 3, that is, 6=2x3. The encryption protocol is constructed in such a way that to decrypt the message, the enemy needs to break down a very large number (not 6!). ), which is currently impossible.

If computing devices are built for this, and current encryption methods are easy to crack, then our current privacy paradigm needs to be reconsidered. This is the case with quantum computers (once operational quantum computers exist): they should be able to break RSA because there is a quantum algorithm that can efficiently break down. While classical computers may require the age of the universe to solve such problems, an ideal quantum computer should be able to do so in a matter of hours or even minutes.

That's why cryptographers are developing solutions to replace RSA and gain quantum-secure security, a cryptographic protocol that targets enemy security that can access quantum computers. There are two main approaches to this: post-quantum cryptography and quantum key distribution.

How to encrypt information in a world equipped with quantum computers

Post-quantum cryptography maintains a security paradigm based on complexity. One should look for mathematical problems that quantum computers still struggle to solve and use them to build cryptographic protocols, an idea that again makes enemies crack them only after a very long period of time. Researchers are working to develop algorithms for post-quantum cryptography. In fact, the National Institute of Standards and Technology (NIST) initiated a process to solicit and evaluate these algorithms, and in July 2022 announced selected candidate algorithms.

Post-quantum cryptography has a very powerful advantage: it is software-based. Therefore, it is cheap and, more importantly, its integration with existing infrastructure is very simple, as only the previous protocol, such as RSA, needs to be replaced with a new one.

But post-quantum cryptography also carries obvious risks: our confidence in the "hardness" of the chosen algorithm for quantum computers is limited. It is important to remember here that, strictly speaking, no complexity-based encryption protocol has been proven to be secure. In other words, there is no evidence that they cannot be effectively solved on classical or quantum computers.

This is the case with decomposition: the discovery of an effective factorization algorithm that will enable classical computers to decompose RSA without the need for a quantum computer cannot be ruled out. Although unlikely, this possibility cannot be ruled out. In the case of new algorithms, evidence for their complexity is much more limited because they have not yet been intensively tested against clever researchers, let alone quantum computers. In fact, the quantum-safe algorithm proposed in the NIST program was later hacked on a standard PC for an hour.

Secure communications with the laws of quantum physics

The second method of quantum-secure security is quantum key distribution. Here, the security of the protocol is no longer based on complexity considerations, but on the laws of quantum physics. So we talk about quantum physical security.

Without going into the details, keys are distributed using qubits, and the security of the protocol follows the Heisenberg uncertainty principle, which means that any intervention by an eavesdropper will be detected as the state of these qubits is modified. The main advantage of quantum key distribution is that it is based on quantum phenomena that have been verified in many laboratories.

The main problem with adopting it is that it requires new (quantum) hardware. Therefore, it is expensive and integration with existing infrastructure is not easy. However, important initiatives are taking place to deploy quantum key distribution on a European scale.

Which approach to take? This question is often presented as an either/or option, and even in this post, you may have given that impression. However, our vision is that the right approach is to look for a combination of post-quantum and quantum key distribution. The latter shows us that quantum physics provides us with new tools and recipes to truly protect our secrets. If these two methods are combined, hackers will face more difficult times because they will have to face complex computational problems and quantum phenomena.