Post-quantum cryptography: Inria well represented at NIST

The quantum computer is of major importance in cryptography

Building a quantum computer capable of performing certain calculations beyond the scope of classical computers is a major advance that has been foreseen for several decades. However, this possibility has become more tangible, as evidenced by recent advances made possible by considerable public and private investment, such as the European initiative Quantum Flagship. The construction of such a computer would have a cataclysmic effect on the world of cryptography.

This is because, of the cryptographic algorithms that currently protect our communications, most of those that make it possible for two parties to exchange a secret key to initiate secure communication, and the vast majority of digital signature methods, base their security on the difficulty of solving certain problems such as factoring large numbers. But these problems could be solved much more easily by a quantum computer, and increasing the size of the involved numbers would have little effect on the complexity.

The advent of a quantum computer would make it necessary to replace numerous public-key cryptographic algorithms (such as RSA and the Diffie–Hellman protocol) with systems based on other types of difficult problems. These alternative systems must be defined now because it is crucial to evaluate their security before applying them on a wide scale, a process which takes several years. Moreover, some sensitive data must remain protected for several decades, a likely timeline for building a quantum computer. 

Seven Inria candidates selected in the NIST competition

That is why NIST, the American standards institute, launched an international initiative to standardise so-called post-quantum cryptographic algorithms, i.e. algorithms that could also resist adversaries with access to a quantum computer. This standardisation process took the form of an international competition in which all volunteers were invited to submit, in November 2017, new key exchange algorithms and digital signature schemes. NIST accepted 69 submissions as valid candidates, of which 12 were submitted by researchers from Inria project teams. These candidates have since been made public and their security is currently being analysed in great detail by the entire cryptographic community. On the basis of these initial evaluations, last January NIST selected 26 submissions for the next stage of the competition, of which more than a quarter were designed by Inria project-teams.

The seven Inria proposals are the result of a strong line of research developed by the ARIC, SECRET, POLSYS and GRACE project-teams on the possibility of basing cryptographic systems on problems other than those traditionally used. There remain several years of analysis, after which this standardisation initiative should be completed around 2022.

The seven candidate algorithms submitted by Inria are based on different types of difficult algorithmic problems. They can be categorised as follows:

• Candidate algorithms based on problems derived from coding theory: BIKE, Classic McEliece, and ROLLO (involving the SECRET project team).
• Candidate algorithms based on Euclidean lattice-based problems: CRYSTALS-DILITHIUM and CRYSTALS-KYBER (involving the ARIC project team).
• Candidate algorithm based on isogenies of an elliptic curve: SIKE (involving the GRACE project-team).
• Candidate algorithm based on the resolution of multivariate polynomial systems: GeMSS (involving the POLSYS project-team).