NIST announces the winners of the post-quantum competition

Firstly, a bit about cryptography. Cryptography is a technique of crucial importance to the security of the Internet, both because it ensures the confidentiality of communications by encrypting them, and because it guarantees the authenticity of messages thanks to a digital signature. Cryptography is based on mathematics, using operations that are easy to perform when you know a certain secret, the key, but which are incredibly difficult to carry out without this vital piece of information. In theory, it is possible to perform the operation even without by trying an endless range of possibilities (what is known as ‘brute force’), but that would take an infinite amount of time in comparison to our lifespan.

Cryptography, like any security technique, is not infallible. Most successful attacks against cryptographic systems do not target the algorithms themselves but their implementation, for example via a program bug. But weaknesses in the algorithms can also be a source of concern, and cryptanalysis – the art of attacking cryptographic algorithms – regularly ‘cracks’ algorithms. That said, the ‘big’ cryptographic algorithms like RSA and AES have always resisted, sometimes by increasing their key size to improve the safety margin. An effective technique given that the difficulty escalates much faster than the key size, so by doubling the latter you more than double the first.

But this only applies to cryptanalysis programs operating on classical computers, like the one you’re using right now to read this article. Quantum computers have begun to emerge in recent years, however, which can solve difficult problems in a much shorter time thanks to the surprising properties of quantum physics. What’s more, the time it takes to solve them does not increase in the same proportions in relation to key size. The day usable quantum computers appear, cryptographic algorithms like RSA will become obsolete. We often see sensationalist articles in the media surrounding this topic that talk about the ‘quantum apocalypse’.

But when will these computers come into use? There is no easy answer, and predictions range from ‘less than ten years’ to ‘fifty years minimum’. This is because their development requires extremely complex physics and engineering problems to be solved. Not only are current quantum computer prototypes a long way off the required capabilities, but attempts to predict when such computers might be available amount to little.

Which does not mean that nothing should be done in the meantime, as the development and roll-out of solutions will likely take time, often many years. Which means we need to start now. Hence the work of many research teams in the sphere of post-quantum algorithms. These are cryptographic algorithms to which no cryptanalysis solution is known, even with the aid of a quantum computer. And given the time needed to develop, analyse and put in place cryptographic algorithms, saying the starting point needs to be now is no overstatement.

Which is why NIST, National Institute of Standards and Technology, which sets technical standards in various fields, launched a competition in 2016 to select post-quantum cryptographic algorithms to standardise and which will therefore doubtlessly be favoured by many Internet players. Indeed, there are a large number of candidate algorithms (the imagination of mathematicians knows no bounds) and it is important to choose carefully. A post-quantum algorithm that can be ‘cracked’ in the space of a few years by cryptanalysis would not constitute progress. Hence the idea behind the competition, which drew diverse submissions from numerous teams (including several French teams, see this interview with a mathematician in CNRS news). Next, competitors and researchers not participating in the competition analysed the flaws in the proposals, and those with irremediable weaknesses were withdrawn over the different review phases. The last phase left just four competitors in the running for encryption¹ and three for signatures.

The winners, announced on July 5th, are Kyber for data encryption and Dilithium for data signing. Will they be used by your computer in the coming weeks? No, as there are still stages to complete. Now this initial decision has been made, NIST needs to write and approve the technical standards². Programmers then need to implement these standards, which is not always easy (in this field, a programming error has serious consequences). It is because of these time frames that the work on post-quantum algorithms needed to be started well before the computers actually become available.

In the case of the Internet, new post-quantum algorithms will need to be included in the cryptographic systems used, like TLS (Transport Layer Security, which, among others, ensures secure web browsing with HTTPS) and DNSSEC, which ensures that domain names give access to authentic information. This will notably be the task of the IETF, a standards organisation in which Afnic is an active participant. Most Internet players do not program cryptography library software themselves (which would be unwise), so they will therefore then need to wait for the new versions of these libraries, including post-quantum algorithms, to be made available. The change is thus not set to happen overnight, but it is important to prepare for the future by laying the necessary groundwork now.

Will the algorithms selected by NIST be universally adopted? Not necessarily. The Internet does not require ‘permission’ and NIST has no authority to impose its choice, except on the administration in its country. NIST’s credibility has taken a serious hit in the wake of revelations that showed that it had deliberately weakened an algorithm used in cryptography, Dual EC DRBG, on the demand of a US intelligence agency. It is partly as a result of this affair that NIST chose to run a public competition, where each phase is open to public scrutiny to minimise the risk of behind-the-scenes manoeuvring. Given the importance of using standardised algorithms, the difficulty in evaluating a cryptographic algorithm oneself, and the fact that there seems to be no standardisation efforts, it is likely that the competition’s ‘winners’ will be widely used.

For details on quantum computers and on post-quantum cryptography, I recommend the ANSSI document “https://www.ssi.gouv.fr/en/publication/anssi-views-on-the-post-quantum-cryptography-transition/ANSSI views on the Post-Quantum Cryptography transition”. These post-quantum algorithms were explained in detail at the 2019 Afnic Scientific Council Open Day (JCSA) For more on quantum technology in general, see the 2019 parliamentary report by French MP Paula Forteza (in French only). Lastly, ICANN published a paper in 2022 notably discussing the future effects of quantum computing on DNSSEC.