Quantum computer: four algorithms designed to resist its threat

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.

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.

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.

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é.