Le NIST publie ses premiers standards post-quantiques

Quels algorithmes pour implémenter la cryptographie post-quantique ? Dans son processus de standardisation, le NIST a priorisé ML-KEM et ML-DSA.

La sécurité de l’un et de l’autre se base sur des problèmes de réseaux euclidiens.
Le premier est un mécanisme d’encapsulation de clés (Module-Lattice-Based Key Encapsulation Mechanism). Il fut soumis au NIST sous le nom CRYSTALS-Kyber. Le second est un schéma de signature (Module-Lattice-Based Digital Signature Algorithm). Son nom d’origine : CRYSTALS-Dilithium.

Fraîchement standardisé (FIPS 203), ML-KEM comprend trois algorithmes principaux (génération, encapsulation et décapsulation de clés). Le temps de calcul est similaire à celui des solutions pré-quantiques, avec une expansion modérée de la taille des messages et des clés échangés.

La sécurité de ML-KEM se fonde sur un problème mathématique lié à la difficulté de trouver des vecteurs courts dans un réseau euclidien structuré.

ML-DSA, également standardisé (FIPS 204), comprend lui aussi trois algorithmes principaux (génération, signature, vérification/validation). Il est relativement facile à mettre en œuvre, mais les signatures sont moins compactes que dans le domaine pré-quantique.

SHA-DSA, solution de secours pour la signature

Le NIST a standardisé, sous l’identifiant FIPS 205, un troisième algorithme : SHA-DSA (Stateless Hash-Based Digital Signature Standard). Il le présente comme un palliatif au cas où ML-DSA se révélerait vulnérable.

SHA-DSA associe les schémas XMSS (eXtended Merkle Signature Scheme) et FORS (Forest Of Random Subsets). Sa sécurité s’appuie sur la difficulté à trouver les images réciproques de fonctions de hachage.

XMSS est lui-même construit sur WOTS (Winternitz One-Time Signature Plus). Il était initialement candidat à la campagne de normalisation. Mais il a finalement fait l’objet d’un processus distinct.

FN-DSA, un quatrième standard en ligne de mire

Le NIST prévoit de publier, d’ici à fin 2024, un brouillon pour une deuxième solution de repli : FN-DSA. Son socle : l’algorithme FALCON, compact et plus efficace de CRYSTALS-Dilithium, mais plus difficile à mettre en œuvre.

Les travaux de normalisation avaient démarré en 2015. Sept ans plus tard, après trois tours de compétition publique, le NIST avait annoncé 7 « finalistes » et 8 « candidats alternatifs ».
De cette liste pourront émerger d’autres standards faisant office de backup dans l’une ou l’autre catégorie. L’institut américain envisage d’en sélectionner un ou deux cette année sur la partie KEM/chiffrement à clés publiques. Sur le volet signature numérique, le NIST avait relancé un appel à propositions en 2022. Il entend en tirer 15 algorithmes qui feront l’objet d’un deuxième round d’évaluation.

Illustration principale © Siarhei – Adobe Stock