La compétition PQC du NIST : processus et critères

Le NIST a lancé le projet de normalisation de la cryptographie post-quantique (PQC) en 2016, directement en réponse à la menace posée par les ordinateurs quantiques. L’algorithme de Shor peut casser RSA et la cryptographie sur courbes elliptiques en temps polynomial sur un ordinateur quantique suffisamment grand. Le NIST a reconnu que la transition de l’infrastructure cryptographique prend des décennies et a donc engagé le processus bien avant que les ordinateurs quantiques ne constituent une menace immédiate.

Le NIST a lancé un appel à soumissions en décembre 2016 et a reçu 82 dossiers complets en novembre 2017. Après l’examen initial, 69 ont été retenus comme candidats du premier tour. Les soumissions couvraient un large éventail d’hypothèses mathématiques : problèmes de réseaux, fonctions de hachage, cryptographie fondée sur les codes, cryptographie fondée sur les isogénies et polynômes multivariés. La diversité des hypothèses constituait un objectif essentiel afin de ne pas mettre tous ses œufs dans le même panier.

Au cours du premier tour, le NIST et l’ensemble de la communauté cryptographique ont soumis les 69 candidats à une analyse approfondie. Les critères comprenaient la sécurité (résistance aux attaques classiques et quantiques), les performances (tailles des clés et des textes chiffrés, vitesse de calcul), la flexibilité (jeux de paramètres pour différents niveaux de sécurité) et la simplicité d’implémentation. En janvier 2019, 26 candidats sont passés au deuxième tour.

Les 26 candidats du deuxième tour ont fait l’objet d’une cryptanalyse plus approfondie et de mesures comparatives des performances. Plusieurs schémas ont été cassés ou affaiblis au cours de ce tour, notamment Rainbow (multivarié) et SIKE (fondé sur les isogénies, bien que SIKE n’ait été cassé qu’au troisième tour). En juillet 2020, 15 candidats sont passés au troisième tour, répartis entre 7 finalistes et 8 candidats de réserve.

Les 7 finalistes du troisième tour étaient Kyber, NTRU et SABER (KEM), ainsi que Dilithium, FALCON, Rainbow et SPHINCS+ (signatures). SIKE était un candidat de réserve, mais a été spectaculairement cassé en 2022. Le NIST a sélectionné Kyber pour la normalisation des KEM en raison de sa conception claire, de ses preuves de sécurité solides et de ses excellentes performances. Dilithium, FALCON et SPHINCS+ ont été sélectionnés pour les signatures.

Le NIST a délibérément sélectionné des algorithmes reposant sur des problèmes mathématiques différents afin de se prémunir contre de futures avancées. ML-KEM et ML-DSA reposent sur Module-LWE (réseaux). FALCON repose sur les réseaux NTRU et l’échantillonnage gaussien. SLH-DSA repose uniquement sur la sécurité des fonctions de hachage. Si une avancée permettait de casser les réseaux, SLH-DSA resterait sûr, assurant ainsi une diversité algorithmique au sein de la suite normalisée.

En 2022, le NIST a ouvert un quatrième tour consacré à la sollicitation de candidats supplémentaires aux signatures, motivé par le souhait d’accroître la diversité des signatures au-delà des schémas fondés sur les réseaux. Les candidats comprenaient MAYO, CROSS, UOV et d’autres schémas fondés sur des hypothèses multivariées et fondées sur les codes. Ce processus s’est déroulé en parallèle de la finalisation des trois premières normes (FIPS 203, 204 et 205).

Le NIST a publié les normes PQC définitives en août 2024 : FIPS 203 (ML-KEM, fondé sur Kyber), FIPS 204 (ML-DSA, fondé sur Dilithium) et FIPS 205 (SLH-DSA, fondé sur SPHINCS+). FIPS 206 (FN-DSA, fondé sur FALCON) devrait suivre. Ces normes doivent désormais être prises en compte par les organismes fédéraux américains et influencent les normes à l’échelle mondiale par l’intermédiaire d’ISO, d’ETSI et de l’IETF.

L’IETF a rapidement intégré la PQC aux protocoles. En 2024, des projets de RFC concernant ML-KEM dans TLS 1.3, SSH et les certificats X.509 étaient en cours. Cloudflare, Google et Amazon ont annoncé leur intention de déployer ML-KEM dans leurs piles TLS. Apple a annoncé PQ3 pour iMessage, utilisant ML-KEM pour assurer une confidentialité persistante post-quantique fondée sur un mécanisme à cliquet, et l’a déployé sur plus d’un milliard d’appareils.

La compétition PQC du NIST a démontré que la normalisation cryptographique ouverte et collaborative fonctionne efficacement. Plusieurs schémas très réputés ont été cassés au cours du processus (GeMSS, SIKE, Rainbow), confirmant l’importance d’une cryptanalyse publique étendue. La compétition a également stimulé le développement d’implémentations matérielles efficaces et de bibliothèques à code source ouvert (liboqs, PQClean), ce qui a accéléré l’adoption.

La normalisation post-quantique n’est pas achevée. Le NIST continue d’évaluer des schémas de signature supplémentaires afin d’accroître la diversité. L’organisme de normalisation financière X9 élabore des normes PQC pour le secteur bancaire. ETSI et ISO alignent leurs travaux sur les FIPS du NIST. Des orientations de migration sont élaborées pour certains secteurs : les soins de santé (implications de HIPAA), la défense (suite CNSA 2.0 de la NSA) et les télécommunications (3GPP pour la 5G et la 6G).

Combien de candidats sont passés des soumissions initiales au tour 2 du concours PQC de NIST ?

NIST a lancé le projet de normalisation du PQC en 2016 et a reçu 69 soumissions complètes. Trois tours d’évaluation ont réduit le nombre de candidats selon des critères de sécurité, de performances et de diversité. Les sélections finales ont été Kyber (ML-KEM, FIPS 203), Dilithium (ML-DSA, FIPS 204), SPHINCS+ (SLH-DSA, FIPS 205) et FALCON (FN-DSA, FIPS 206). Le concours a validé la cryptanalyse ouverte et a abouti à des normes largement adoptées, désormais intégrées aux protocoles TLS, SSH et de messagerie.