Signatures CRYSTALS-Dilithium et Falcon

Les signatures RSA et ECDSA sont cassées par l'algorithme de Shor. Les signatures post-quantiques doivent les remplacer pour les certificats TLS, la signature de code, la signature des courriels (S/MIME, PGP) et l'authentification des mises à jour logicielles. Le NIST a normalisé deux schémas fondés sur les réseaux : ML-DSA et FN-DSA.

Dilithium repose sur la difficulté du LWE modulaire et du SIS modulaire (solution entière courte). Sa preuve de sécurité est formulée dans le QROM (modèle de l'oracle aléatoire quantique). Trois variantes : Dilithium2 (environ 128 bits), Dilithium3 (environ 192 bits) et Dilithium5 (environ 256 bits). Le chemin de signature est simple et ne nécessite pas d'échantillonnage par rejet.

Clé privée : matrices secrètes s1, s2. Clé publique : t = As1 + s2. Signez : échantillonnez y aléatoirement ; calculez w = Ay ; calculez le défi c = H(mu || w1), où w1 = HighBits(w) ; calculez z = y + cs1 ; si ||z|| ou ||r0|| est trop grand, rejetez et recommencez. Produisez (z, c, indice).

Vérifiez (z, c, indice) : assurez-vous que ||z|| est petit ; calculez w' = Az - ct ; utilisez l'indice pour retrouver w1 ; vérifiez c == H(mu || w1). L'indice est constitué d'un petit nombre de bits provenant de MakeHint(). Le rejet garantit que z ne révèle pas s1 : l'argument de sécurité est un argument « abandon puis uniformité ».

ML-DSA-65 (Dilithium3, sécurité de 192 bits) : clé publique de 1952 octets, clé privée de 4000 octets, signature de 3293 octets. À titre de comparaison, ECDSA-P256 utilise une clé publique de 64 octets et une signature de 64 octets. Les signatures de Dilithium sont environ 40 à 50 fois plus volumineuses, mais elles résistent aux attaques quantiques.

Falcon repose sur des réseaux NTRU et utilise un échantillonneur gaussien sur le réseau NTRU. Ses signatures sont nettement plus petites que celles de Dilithium, mais la signature nécessite un échantillonneur gaussien à virgule flottante, plus difficile à implémenter en temps constant et plus complexe à coder de manière sûre.

Falcon-512 (sécurité de 128 bits) : clé publique de 897 octets, signature de 666 octets — beaucoup plus petite que celle de Dilithium. Compromis : Falcon est plus difficile à implémenter de manière sûre (l'échantillonnage gaussien est sensible aux attaques temporelles). Il convient aux environnements à bande passante limitée, mais nécessite une implémentation soignée.

SPHINCS+ est un schéma de signature fondé sur les fonctions de hachage, un choix conservateur qui ne repose sur aucune hypothèse algébrique structurelle. Sa sécurité dépend uniquement de la sécurité de la fonction de hachage. Taille des signatures : environ 8 à 50 Ko, ce qui est volumineux. Signature lente. Utilisé lorsque la confiance à long terme est essentielle et que les performances sont secondaires.

ML-DSA (Dilithium) : usage général, implémentation simple, adapté aux certificats TLS et à la signature de code. FN-DSA (Falcon) : environnements à bande passante limitée (IoT, LPWAN). SLH-DSA (SPHINCS+) : choix extrêmement conservateur, adapté aux racines à longue durée de vie (clés hors ligne des CA, racine logicielle de confiance).

Dilithium : l'échantillonnage par rejet peut révéler le temps d'exécution d'une branche ; utilisez une comparaison en temps constant. Falcon : l'échantillonneur gaussien utilise la virgule flottante ; assurez le déterminisme de FP. Pour les deux : évitez les canaux auxiliaires dans l'arithmétique polynomiale. Utilisez les implémentations de référence des paquets de soumission au NIST.

NIST FIPS 204 : ML-DSA (Dilithium). NIST FIPS 205 : SLH-DSA (SPHINCS+). NIST FIPS 206 : FN-DSA (Falcon). Toutes ont été publiées en août 2024. Bibliothèques : OpenSSL 3.x, BoringSSL et liboqs (projet Open Quantum Safe) implémentent les trois.

Quel est le principal avantage de Falcon par rapport à Dilithium ?

ML-DSA (Dilithium) : fondé sur les réseaux, simple, signatures d'environ 3 Ko. FN-DSA (Falcon) : fondé sur NTRU, signatures d'environ 700 octets, implémentation complexe. SLH-DSA (SPHINCS+) : fondé sur les fonctions de hachage, conservateur, volumineux. Tous sont normalisés dans FIPS 204/205/206. Ensuite : migrer vers la PQC au moyen d'approches hybrides.