The quantum apocalypse is not yet upon us, but we need to be ready for it

Over the past few years, as market players and research laboratories have made announcements, a number of experts have been asking whether the advances made in quantum computing will one day make it possible to break today’s encryption algorithms. The stakes are colossal. For example, if the keys to the most well-known of these algorithms – RSA – were to be broken, the security of the entire public Internet would teeter on the brink of collapse.

Today, the security of all our digital communications and transactions is based on public key cryptography (PKC). PKC makes secure communications between users or servers possible. It implements two main functions: establishing secure channels (key establishment) and authenticating digital information.

“These techniques are based on two mathematical problems: factoring large numbers and calculating the discrete logarithm. These are designed to be impossible to solve within a reasonable timescale, given current computing resources and mathematical knowledge. For example, the RSA public key algorithm, which is widely recognised and deployed, is based on factoring large numbers,” ANSSI (the French National Cybersecurity Agency) states in a memo from 2022.

However, if a quantum computer were to be developed, factoring large numbers and calculating discrete logarithms could be solved within more than reasonable timescales – within a few days, or even just a few hours. This would inevitably lead to a collapse in the security of public key cryptography currently deployed around the world, putting the confidentiality and integrity of digital communications on the Internet and elsewhere at risk.

Shor’s algorithm: gateway to the potential collapse of public key cryptography

Shor’s algorithm, developed by American mathematician Peter Shor, has been around since 1994 and is expected to precipitate this collapse. This algorithm can solve extremely complex mathematical problems, including factoring large numbers. As Shor’s algorithm is a quantum algorithm, it cannot be run on conventional computers. But if true quantum computers were ever to emerge, they would be able to run it.

The quantum computer prototypes that exist right now are still far from having the capacity and stability required to achieve this technological feat. “I am extremely sceptical and cautious about the possibility of a quantum computer being able to break an RSA key. This would require quantum computers with a very large number of qubits – at least a few hundred thousand – with qubit quality that we do not have today and are no where near having. There is a huge technological hurdle to overcome before we get there,” explains Olivier Ezratty, a quantum computing expert and author of the book Understanding Quantum Technologies.

It is nevertheless essential to prepare for the arrival of true quantum computers, which experts refer to as CRQCs, or Cryptographically Relevant Quantum Computers, as opposed to current quantum computers, known as NISQs, or Noisy Intermediate-Scale Quantum computers.

The reason we need to “prepare for the worst” is simple: attackers could launch retroactive attacks. These Store Now, Decrypt Later attacks involve capturing encrypted communications now with a view to decrypting them later. In some, admittedly rare, situations, this could pose a threat to information that needs to be protected over the long term, such as data in the defence and healthcare sectors.

Post-quantum cryptography to avert an apocalypse

This is why the quantum threat is taken very seriously by all those countries at the forefront of the field. In the United States, the National Institute of Standards and Technology (NIST) launched an international call for contributions in 2016 called “Post-Quantum Cryptography Standardization”. Initially, several dozen encryption algorithms were selected, all capable of withstanding attacks from CRQCs. During the third round, which ended in July 2022, only four of these post-quantum algorithms remained.

French researchers are heavily involved in this work. The CRYSTALS-Kyber algorithm is the only one selected for public key encryption and key establishment algorithms. A consortium including Damien Stehlé, professor at ENS Lyon and member of the Computer Science and Parallelism Laboratory (LIP–CNRS/ENS Lyon/Claude Bernard University Lyon 1), is working on this project.

Stehlé is also involved in CRYSTALS-Dilithium, an algorithm which will be used to generate electronic signatures. Two other algorithms were shortlisted in this category, including Falcon, a project involving Pierre-Alain Fouque, professor at the University of Rennes 1 and member of the Institute for Research in Computer Science and Random Systems (IRISA–CNRS/University of Rennes 1).

For ANSSI, post-quantum cryptography also holds the most promise for protecting against the quantum threat. “Post-quantum cryptography is a family of cryptographic algorithms including key establishment and digital signatures that provides conjectured security [for which no effective quantum attack exists today, editor’s note] against the quantum threat, in addition to their traditional security. Post-quantum algorithms can be run on conventional devices and computers. They can therefore be deployed on existing infrastructure and communications channels without any major hardware changes, unlike quantum key distribution. Furthermore, these algorithms are not only designed to be used after a CRQC has been built; they can also be readily deployed in advance,” says ANSSI.

Olivier Ezratty is equally reassuring: “By the time a quantum computer is capable of breaking an RSA key, the whole world will have deployed the technologies needed to protect against it. NIST’s standardisation efforts are designed to replace RSA keys with modern public keys that would withstand the pounding of any quantum computer.”

But beware, warns ANSSI. Although NIST’s new post-quantum toolbox may seem a boon for developers, the level of maturity of post-quantum algorithms must not be overestimated. “There is still a lack of cryptanalytical insight into various aspects of their security, or they are still very much at the research stage, whether this involves analysing the difficulty of the underlying problem in traditional and quantum security models, scaling, integrating algorithms into communication protocols or, even more importantly, designing secure implementations. This situation will continue for some time after the publication of NIST’s standards,” concludes ANSSI.