Quantum computer: four algorithms designed to resist its threat

Changed on 21/12/2022
At the beginning of July 2022, the NIST unveiled the four algorithms that will be standardized to protect against attacks from quantum computers. Researchers Damien Stehlé (AriC project-team) and Pierre-Alain Fouque (CAPSULE project-team), co-authors respectively of CRYSTALS-Kyber and CRYSTALS-Dilithium for the former and FALCON for the latter, come back on the origin and importance of this certification.
© Flickr / Photo Pierre Metivier


The NIST (National Institute of Standards and Technology) launched an international call for contributions in July 2016 to identify the best candidates for future post-quantum cryptography standards, i.e. resistant to tomorrow's quantum computers. After six years of competition, the U.S. government agency thus presented in early July the first group of cryptographic algorithms designed to resist the threat of a future quantum computer.

These are CRYSTALS-Kyber for public key encryption and key establishment algorithms, and CRYSTALS-Dilithium, FALCON and SPHINCS+ for electronic signature generation.

Why is this an important step in securing our data?

In 1994, the American mathematician Peter Shor shook up the world of computer security by discovering a technique (later named "Shor's algorithm") capable of considerably reducing the time needed to solve the difficult problems on which public key cryptography security is based, thus making it possible to efficiently break codes that generally resist for thousands of years. Thus, all devices using RSA or elliptic curves would become breakable by a third party if Shor's algorithm were ever programmed into a quantum computer.

Since then, many scientists have predicted the more or less distant arrival of a quantum computer capable of breaking a cryptographic protocol within a reasonable time. However, rapid advances in quantum technology now make these machines much closer to us than they were in the mid-nineties, bringing current cryptographic protocols closer to their expiration date. In other words: what exists today will be broken by a sufficiently powerful quantum computer.

"We are still a long way from that, current quantum computers are not very expressive. They can do better than classical computers, but only for a given problem, built specifically. But it is possible that we will build an efficient quantum computer in a few years," explains Pierre-Alain Fouque, professor at the University of Rennes 1, member of IRISA (Inria/CNRS/University of Rennes 1) and co-author of FALCON.

"It's important to get ahead of the curve because the transition is likely to be very long, since we're talking about all software that encrypts or signs. It's going to be years before everyone has made the move. Moreover, the most important threat at the moment consists in retaining the information that is in transit today in order to decrypt it quickly when we have a quantum computer," adds Damien Stehlé, professor at the ENS in Lyon, member of the LIP (Inria/CNRS/ENS in Lyon/Université Claude Bernard Lyon 1) and co-author of CRYSTALS-Kyber and CRYSTALS-Dilithium.

These advances prompted the NSA to announce, in 2015, that it was becoming urgent to seriously consider alternatives to current cryptography, and then the NIST, in 2016, to launch a competition to develop such "quantum-resistant" algorithms. In total, nearly 70 submissions to the competition were received by NIST, with four currently selected.

Alternatives to existing schemes

Of these four selected algorithms, three use Euclidean networks, whose use in cryptography really started in the mid-nineties (in the eighties, networks were used in cryptanalysis (to break cryptosystems). Cryptographers were then interested in providing alternatives to RSA mechanisms based on problems that were difficult for the adversary (error-correcting code, solving multivariate systems, Euclidean networks). These alternative mechanisms, continued a parallel existence to RSA or elliptical networks without much interest in their implementation.

"It wasn't a mainstream topic at the time, then in the 2000s there was some fundamental work on the subject, and it really started in 2005. At that point I was finishing my thesis and I got interested in it when the big seminal results were starting to come out. It was not at all practical at the time, it only existed on paper, but a community developed around it, the foundations were established, and gradually it became more complete," says Damien Stehlé.

An alternative that proved to have good properties. "The first algorithms presenting an alternative to RSA mechanisms were not easily exploitable, so there was a lot of research to make them usable. The messages are still a little long, but today we have real alternatives to the cryptography currently used," says Pierre-Alain Fouque.

Why did NIST select two signature schemes based on Euclidean networks?

Each of the two signature schemes selected has advantages and disadvantages. There is no scheme today that can be good at all levels. It is therefore necessary to offer solutions designed for different situations.

Towards a concrete use

The four cryptographic protocols selected by NIST will now become part of the NIST Postquantum Cryptographic Standard, which is expected to be finalized in about two years. "This is the culmination of years of work, and it represents a huge international collaborative effort. Doing theoretical research is always fun, that's what we signed up for, but when you have the opportunity for it to be useful, it's satisfying. Part of the work over the next two years will be to describe very precisely how these algorithms work, point by point," explains Damien Stehlé.

"This research has a very theoretical origin, close to both complexity theory and algebraic number theory. The fact that they have ended up leading to very concrete things is a very nice recognition. For the authors, of course, and for all those who have contributed in this field," adds Pierre-Alain Fouque.

In parallel, four other encryption algorithms are being considered for inclusion in the standard, and NIST plans to announce the winners of this round at a later date. NIST is announcing its choices in two stages because of the need for a robust variety of defense tools. Thus, NIST envisions more than one algorithm being standardized for each use case, in case one of them proves vulnerable.

"Encryption and signature are the backbone of cryptography, it's essential. The next big goal of this community is to have protocols that are more advanced than encryption and signature and that are sufficiently optimized to be concrete and deployable," concludes Damien Stehlé.

Focus on the collaborations behind the four NIST-standardized schemes

The CRYSTALS protocols are the result of an international collaboration between ten researchers from ARM Limited, NXP Semiconductors, IBM Research Zurich, CWI Amsterdam, MPI-SP, SRI International, Ruhr-University Bochum (Germany), University of Waterloo (Canada), Radboud University Nijmegen (The Netherlands) and ENS Lyon.

Falcon was created by ten scientists from the University of Rennes, Brown University (USA), IBM Research Zurich, NCC Group, Thales and OnBoard Security.

SPHINCS+ was designed by nineteen researchers from Eindhoven University of Technology (Netherlands), University of Illinois at Chicago (USA), Ruhr University Bochum (Germany), Academia Sinica (China), Katholieke Universiteit Leuven (Belgium), Technical University of Graz (Austria), genua GmbH, Cisco Systems, Google, InfoSec Global, Infineon Technologies, University of Southern Denmark, Radboud University Nijmegen (Netherlands), MPI-SP and Cloudflare.

"The four algorithms selected and the four algorithms selected for the extension of the standardization campaign are the result of international cooperations. But the list of their co-authors and their affiliations are a striking illustration of the extraordinary vitality of French and European research in cryptography," says ANSSI, in an article about the selection of the four schemes by NIST.

Harold Ollivier, director of the QuantumTech@Inria program, agrees: "The NIST competition clearly illustrates the need to invest in upstream and long-term research: the techniques used by these new algorithms were discovered without any relation to the quantum computer, but are now essential for data security. For this, it was necessary to support an effort whose applications were not yet foreseeable. This is partly what we are trying to do with the QuantumTech@Inria program by recruiting excellent scientists who are experts in quantum information processing".