De 2016 aux FIPS 203 : comment le NIST a choisi la cryptographie post-quantique

Le National Institute of Standards and Technology mène depuis 2017 un processus de sélection et de normalisation de la cryptographie post-quantique. La raison est concrète : selon les estimations, l'algorithme RSA, largement répandu, pourrait être cassé par un ordinateur quantique dès 2030 environ. Le processus du NIST passe pour la plus importante entreprise collective de conception et d'évaluation d'algorithmes résistants aux attaques quantiques. Il se déroule en plusieurs tours, chacun accompagné d'une conférence. À chaque tour, une partie des algorithmes est écartée, les autres passent à des examens plus poussés.

La plupart des primitives cryptographiques symétriques s'adaptent assez facilement à la sécurité quantique. Il suffit par exemple de doubler la longueur de clé pour neutraliser l'accélération qu'apporte l'algorithme de Grover. Les efforts se concentrent donc sur la cryptographie asymétrique, en particulier sur les signatures numériques et les mécanismes d'encapsulation de clé. Les futurs standards paraissent sous forme de Federal Information Processing Standard, notamment FIPS 203, FIPS 204 et FIPS 205.

Un modèle repris de l'AES

Le format éprouvé, ouvert et transparent de l'entreprise a été calqué sur le processus de normalisation de l'AES des années 1997-2000, salué par le milieu cryptologique. Les travaux universitaires sur l'impact possible de l'informatique quantique remontent au moins à 2001. En 2015, les autorités fédérales américaines ont annoncé leur intention de faire passer tous les systèmes gouvernementaux de traitement de l'information soumis à des exigences de confidentialité à une cryptographie résistante aux ordinateurs quantiques. C'est pourquoi, à la conférence PQCrypto de 2016, le NIST a annoncé la normalisation de primitives cryptographiques sûres face au quantique. En décembre 2016, le processus a été inauguré par un appel à propositions.

À la clôture de l'appel, fin 2017, 23 systèmes de signature numérique et 59 méthodes de chiffrement et d'encapsulation de clé avaient été déposés. Sur ce total, 69 ont été jugés complets et aptes à participer au premier tour, et 23 candidatures ont été retenues pour la suite des travaux. Sept algorithmes et huit candidatures alternatives ont franchi le deuxième tour. Le 22 juillet 2020, le NIST a annoncé sept finalistes, dont trois systèmes de signature, ainsi que huit solutions alternatives.

Qui a gagné, qui est tombé

Au troisième tour, CRYSTALS-Kyber l'a emporté comme mécanisme d'encapsulation de clé, et CRYSTALS-Dilithium, FALCON et SPHINCS+ comme systèmes de signature numérique. Ce sont eux que le NIST normalise aujourd'hui. Le quatrième tour, annoncé en juillet 2022, examine quatre autres algorithmes ; il était encore en cours en mars 2024. En 2024, le NIST a publié les versions définitives de ses trois premiers standards de cryptographie post-quantique. Deux algorithmes fondés sur les réseaux euclidiens, ML-KEM, connu du grand public sous le nom de Kyber, et ML-DSA, connu sous celui de Dilithium, figurent parmi les premières solutions post-quantiques normalisées. Toutes les constructions n'ont pas survécu : la construction SIDH/SIKE, très commentée, a été cassée de façon spectaculaire en 2022. L'attaque ne concernait toutefois que cette famille de schémas et ne se généralise pas aux autres constructions fondées sur les isogénies.