Ring-LWE et réseaux modulaires

Le LWE standard nécessite de grands produits matrice-vecteur, ce qui entraîne des clés volumineuses. Ring-LWE, introduit par Lyubashevsky, Peikert et Regev en 2010, remplace les vecteurs et les matrices par des polynômes dans un anneau R_q = Z_q[X]/(f(X)). Ce cadre structuré permet d’obtenir des clés beaucoup plus compactes et des calculs arithmétiques plus rapides, faisant de Ring-LWE le fondement pratique de la cryptographie sur réseaux utilisée dans le monde réel.

Le polynôme f(X) utilisé dans Ring-LWE est généralement f(X) = X^n + 1, où n est une puissance de 2. Il s’agit du polynôme cyclotomique d’ordre 2n. Il est choisi parce qu’il est irréductible sur Z, garantit que l’anneau R_q possède de bonnes propriétés algébriques et permet la transformée théorique des nombres (NTT) pour effectuer efficacement les multiplications. Les anneaux cyclotomiques ont été étudiés en profondeur et sont considérés comme sûrs.

Dans Ring-LWE, le secret s est un polynôme de R_q et les échantillons prennent la forme (a, b = a*s + e), où a est un élément aléatoire uniforme de l’anneau et e est un petit polynôme d’erreur. L’adversaire observe de nombreux échantillons de ce type et doit retrouver s ou les distinguer d’échantillons uniformes. La difficulté repose sur l’hypothèse Ring-LWE, qui bénéficie d’une réduction à partir de problèmes du pire cas sur des réseaux idéaux.

Ring-LWE est plus difficile pour un adversaire, mais s’accompagne aussi d’une réduction de sécurité légèrement différente de celle du LWE classique. La réduction part de problèmes du pire cas sur des réseaux idéaux (ideal-SVP), et non de réseaux quelconques. La structure supplémentaire des réseaux idéaux pourrait en principe les rendre plus faciles que les réseaux généraux, et cette question fait l’objet de recherches actives. Aucune attaque pratique exploitant cette structure n’est connue.

Module-LWE (M-LWE) généralise à la fois LWE et Ring-LWE en utilisant une matrice k x k d’éléments d’un anneau plutôt qu’un seul élément d’un anneau ou une grande matrice d’entiers. Lorsque k = 1, il se réduit à Ring-LWE ; à mesure que k augmente, il se rapproche du LWE standard. Ce paramètre ajustable k permet d’équilibrer la confiance dans la sécurité et les performances.

CRYSTALS-Kyber, désormais ML-KEM et défini par FIPS 203, est fondé sur Module-LWE avec une matrice de rang k sur R_q. Le paramètre k contrôle directement le niveau de sécurité : k=2 vise une sécurité de 128 bits (ML-KEM-512), k=3 vise 192 bits (ML-KEM-768) et k=4 vise 256 bits (ML-KEM-1024). La structure modulaire permet d’utiliser une seule base de code, avec un niveau de sécurité ajusté en modifiant k.

La multiplication de polynômes dans R_q = Z_q[X]/(X^n + 1) constitue le principal goulot d’étranglement en matière de performances. La transformée théorique des nombres (NTT) est une transformée de Fourier discrète sur Z_q qui convertit les polynômes en une forme évaluée, où la multiplication devient une opération terme à terme. Lorsque q est choisi de façon à permettre l’application de la NTT, la multiplication de polynômes s’effectue en O(n log n) au lieu de O(n^2), ce qui constitue une optimisation essentielle dans ML-KEM et ML-DSA.

La NTT exige que q soit un nombre premier tel que q = 1 mod 2n, ce qui garantit que Z_q contient une racine primitive 2n-ième de l’unité. Pour ML-KEM avec n = 256, q = 3329 satisfait cette exigence. La NTT sur Z_3329 est extrêmement rapide sur le matériel moderne doté d’instructions SIMD, ce qui permet d’effectuer des milliers d’opérations ML-KEM par seconde sur des processeurs grand public.

Ring-LWE et Module-LWE réduisent considérablement la taille des clés par rapport à LWE standard. Une clé publique LWE standard offrant une sécurité de 128 bits peut peser 1 MB ; Ring-LWE ramène cette taille à environ 800 octets, tandis que Module-LWE (ML-KEM-768) permet d’obtenir une clé publique de 1184 octets avec une sécurité post-quantique de 192 bits. Cette compacité rend les schémas fondés sur les réseaux pratiques pour TLS et les systèmes embarqués.

Certains cryptographes craignent que la structure algébrique supplémentaire des anneaux cyclotomiques permette des attaques qui ne s’appliqueraient pas à LWE classique. En 2024, Elias Rokicki et ses collaborateurs ont publié une analyse du polynôme cyclotomique d’ordre 2n, ne trouvant aucune exploitation pratique, mais soulignant l’importance d’un examen continu. Le processus PQC du NIST a pris ce risque en compte et a choisi Module-LWE, notamment pour réduire la dépendance à l’égard d’une seule structure en anneau.

Au-delà de Kyber, Ring-LWE est à la base de CRYSTALS-Dilithium (ML-DSA), le schéma de signature normalisé par le NIST. La bibliothèque SEAL de Microsoft permet le chiffrement homomorphe au moyen de Ring-LWE. La bibliothèque de cryptographie Tink de Google prend en charge ML-KEM. Ring-LWE est passé d’une construction théorique à un déploiement en production en un temps remarquablement court, sous l’impulsion du processus de normalisation du NIST.

Quel est le principal avantage de Ring-LWE par rapport à LWE standard ?

Ring-LWE transpose LWE dans l’anneau polynomial R_q = Z_q[X]/(X^n+1), ce qui réduit considérablement la taille des clés et permet une arithmétique rapide fondée sur la NTT. Module-LWE généralise cette construction avec une structure de rang k, à la base de ML-KEM (FIPS 203) et de ML-DSA (FIPS 204). Le nombre premier q = 3329, adapté à la NTT, permet une implémentation efficace. La sécurité repose sur la difficulté des problèmes définis sur les réseaux idéaux et modulaires.