How will we protect ourselves from an enemy with a quantum computer? Cryptographers are developing solutions to achieve “quantum security,” as researcher Antonio Acín explains in The Conversation.
Thirteen, 53, 433…the size of quantum computers is given in terms of quantum bits, or “qubits”. It has increased considerably in recent years thanks to major public and private investments. Clearly, we should not focus only on their quantity, because the quality of the qubits that we manage to prepare is as important as their number for a quantum computer to one day surpass our current classical computers – we are talking about reaching “the quantum advantage”. Yet, it is conceivable that quantum computing devices offering such an advantage will become available in the near future. How would this affect our daily life?
It is never easy to make predictions, but it is recognized that the cryptography will be modified by the advent of quantum computers. It has become commonplace to say that the protection of privacy is an essential issue in our information society: every day, large quantities of confidential data are exchanged, for example via the Internet. The security of these transactions is crucial and depends mainly on a single concept: complexity, or more precisely, IT complexity. Confidential information remains secret because any enemy or spy willing to read it must 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 remains safe in practice, because solving the problem and then hacking the protocol would take a ridiculously long time (years, even several thousand years, for example).
The most emblematic example of this approach is the RSA protocol (for its inventors Ron Rivest, Adi Shamir and Leonard Adleman), the scheme used today to secure our information transmissions (eg banking transactions). Its security relies on the fact that we do not know of an efficient algorithm for factoring large numbers. While factoring is an easy math problem that many of us have encountered in school (given a large number, the goal is to find two numbers whose product is equal to the original number, leaving out the trivial solution given by the initial number and one – for example, if the initial number is 6, the solution is 2 and 3, because 6=2×3), cryptographic protocols are constructed in such a way that the enemy, for decrypt the message, must factorize a very large number (not 6!), which is currently impossible in practice.
But if more powerful computing devices are built, for which the mathematical problems currently used for cryptography are easy to solve, our current privacy paradigm must be rethought. In other words, while classical computers can take insane amounts of time to solve the most difficult versions of a problem (the age of the universe, for example), quantum computers ideals should be able to do it in minutes…or, if we consider more realistic models of quantum computers, maybe in hours.
This is why cryptographers are developing solutions to replace RSA and achieve “quantum security”, i.e. cryptographic protocols that are secure against an enemy who has access to a quantum computer. To do this, there are two main approaches: post-quantum cryptography and the quantum key distribution.
What is post-quantum cryptography?
Post-quantum cryptography maintains the complexity-based security paradigm: we look for mathematical problems that remain difficult even for quantum computers, and we use them to build cryptographic protocols. The idea is still that an enemy needs a ridiculously long time to hack the protocol. Researchers are hard at work developing post-quantum cryptography algorithms, and NIST (the US National Institute of Standards and Technology) has launched a process to solicit and evaluate these algorithms. The chosen candidates were announced in July 2022.
Post-quantum cryptography has one major advantage: it is software-based. It is therefore inexpensive and, above all, its integration into existing infrastructures is simple, since it suffices to replace the previous protocol, for example RSA, with the new one.
But post-quantum cryptography also presents an obvious risk: our confidence in the “difficulty” of new algorithms in the face of quantum computers is limited. Indeed, it should be remembered that it is not proven that none of the cryptographic protocols based on the notion of complexity is safe: there is no (mathematical) proof that they cannot be solved efficiently on a classical or quantum computer!
This is for example the case of factorization. It cannot be ruled out that a classical algorithm for efficient factorization will one day be found – in which case protocol-based security would collapse, even without a quantum computer. This is believed to be unlikely, as (very clever) researchers have been searching for centuries for an efficient algorithm for factorization, without success. But we can’t rule it out.
In the case of the new algorithms, the proof of their complexity is much more limited, because they have been invented recently and they have not yet been tested much – neither by researchers (always very intelligent) nor by a quantum computer (because none are available). Sometimes the difficulty tests are quite fast: one of the algorithms proposed in the NIST initiative was subsequently cracked in an hour on a standard PC.
Quantum physical security to secure communications
The second approach to quantum security is the quantum key distribution. Here we have a paradigm shift, since protocol security is no longer based on complexity considerations, but on the laws of quantum physics. So we’re talking about security. quantum physics.
Without going into details, a secret key is distributed using qubits and the security of the protocol derives from the Heisenberg uncertainty principle, which implies that any intervention by the spy is detected because it changes the state of these qubits.
The main advantage of quantum key distribution is that it is based on quantum phenomena, which have been verified in many experimental laboratories.
The main problem for its adoption is that it requires new (quantum) hardware. It is therefore expensive and its integration into existing infrastructures is not easy. However, important initiatives are underway, for example for the deployment of quantum key distribution on a European scale.
Combine software and hardware
Which approach to adopt? This issue is often presented as a dichotomy and even this article may have given that impression so far. In fact, I think the way forward is to combine quantum (see hardware) and post-quantum (software way) key distribution. Quantum key distribution has shown us that quantum physics provides us with new tools and recipes to secure our secrets, beyond standard complexity arguments. If the two approaches are combined, hackers will have a much harder time hacking security protocols, as they will have to deal with both complex computational issues and quantum phenomena.
Antonio Acín, Professor and group leader
This article is republished from The Conversation under a Creative Commons license. Read the original article.