the issues around the four algorithms selected by the NIST

This is the operating theory of a quantum machine, but it is still necessary to have algorithms capable of exploiting this new way of working. Here again, the “revolution” is not new: in 1994, mathematician Peter Shor presented an eponymous algorithm capable of factoring any number.

And then will you tell me? The consequences are very important since this algorithm can in theory “ break most of the current cryptographic systems, from the encryption of our banking transactions to the codings allowing the exchange of state secrets, which are based precisely on the explosion in calculation time of factorization for increasingly large numbers “.

From several billion years to… a few minutes

Whereas a classical computer would need billions of years to factorize a large number, a quantum machine would only take a few minutes. We’re not there yet, and known machines don’t have enough qubits to be worrying about.

If quantum can be very useful for asymmetric algorithms (i.e. with a public key and a private key) based on factorization – RSA for example –, this is not the case with symmetric algorithms (with a secret key). In this case, the impact of a quantum computer is limited ” since it suffices to double the size of the keys in symmetric cryptography “says Bernard Ourghanlian, technical director of Microsoft France. We discussed this topic in our first magazine, now free to download.

We sometimes speak of quantum supremacy, which corresponds to the moment when quantum machines will take over the others. Google claims to have reached this barrier, while IBM refutes. Supremacy or not, it is not the most important: we are at a crossroads » and know « whether we passed the bifurcation point or not exactly, that’s not where the debate is “, recently explained Philippe Chomaz, Scientific Director at the CEA’s Fundamental Research Department.

The post-quantum has been preparing for years

Since this new technology is already several decades old, the world has had plenty of time to prepare. As early as 2016, Google, for example, began testing post-quantum algorithms, that is to say when quantum computers will have arrived in earnest. Microsoft also launched several years ago. In France, the Quantum Plan provides 150 million euros dedicated to post-quantum cryptography.

The CNRS recalls that the objective of post-quantum cryptography is not only to develop systems resistant to both quantum and classical computers, but also ” that can interact with existing communication protocols and networks “.

Either way, time is against us. It doesn’t matter if a quantum computer arrives in a week or ten years, malicious actors and/or intelligence agencies are not waiting to collect and store data, with a view to decrypting it one day using quantum computers. .

Four algorithms selected by NIST

It is in this artistic vagueness that the National Institute of Standards and Technology (NIST), of the American Department of Commerce, has justannounce (as expected) the first four algorithms that will be part of NIST’s Post-Quantum Cryptographic Standard. She ” should be finalized in about two years “.

This is an opportunity for the INS2I (Institute of Information Sciences and their Interactions) of the CNRS to put itself forward: ” Three of the four selected algorithms […] have received contributions from laboratories attached to INS2I, and a new submission phase (round 4) involves several other CNRS laboratories “.

The announcement follows an initiative launched in 2016, after NIST called on the world’s cryptographers to design and then verify encryption methods ” able to withstand an attack from a future quantum computer more powerful than the relatively limited machines available today “.


For public key encryption and key establishment algorithms, the only algorithm retained is CRYSTALS-KYBER “, indicates the CNRS. ” Among its advantages are relatively small encryption keys that two parties can exchange easily, as well as its speed of execution. “, adds the NIST.

For digital signatures, used when we need to verify identities during a digital transaction or sign a document remotely, NIST has selected three algorithms: CRYSTALS-Dilithium, FALCON and SPHINCS+.

Reviewers have noted the high efficiency of the first two, and NIST recommends CRYSTALS-Dilithium as the primary algorithm, with FALCON for applications that require smaller signatures than Dilithium can provide. The third, SPHINCS+, “ is a bit bigger and slower than the other two », but was retained because it was based on a different mathematical approach.

Four additional algorithms are under consideration for inclusion in the standard, but NIST plans to announce the finalists in this round at a later date.

An agreement between CNRS, NIST and the University of Limoges

Finally, the National Center for Scientific Research announces license agreement between the NIST, the CNRS and the University of Limoges. In effect, ” two of the finalist solutions could be based on patent families filed in 2010 by teacher-researchers Philippe Gaborit and Carlos Aguilar-Melchor (University of Limoges and CNRS Xlim laboratory), and jointly owned by the CNRS and the University of Limoges “.

The Center explains:

the CNRS and the University of Limoges, supported by France Brevets, have agreed on the terms of a license agreement which the stakeholders welcome. The agreement thus makes it possible to promote intellectual property resulting from the results of French public research.

Thanks to the announced license agreement between NIST, CNRS and the University of Limoges, operators and end users of cryptographic standards derived from the selected PQC algorithms will not need to obtain a separate license on this family of CNRS patents. This will promote rapid and widespread adoption of these cryptographic standards, a common goal of NIST and CNRS. “.

In any case, the adventure of quantum computing and post-quantum algorithms has only just begun. The number of qubits is steadily increasing and we will surely reach supremacy one day… it remains to be seen when.

We want to thank the author of this short article for this awesome content

the issues around the four algorithms selected by the NIST

We have our social media pages here and other pages on related topics here.