Ring-LWE und Modul-Gitter

Standard-LWE erfordert große Matrix-Vektor-Produkte, was zu großen Schlüsselgrößen führt. Ring-LWE, 2010 von Lyubashevsky, Peikert und Regev eingeführt, ersetzt Vektoren und Matrizen durch Polynome in einem Ring R_q = Z_q[X]/(f(X)). Diese strukturierte Umgebung ermöglicht deutlich kompaktere Schlüssel und schnellere Arithmetik und bildet dadurch die praktische Grundlage für die reale gitterbasierte Kryptografie.

Das in Ring-LWE verwendete Polynom f(X) ist typischerweise f(X) = X^n + 1, wobei n eine Zweierpotenz ist. Dabei handelt es sich um das 2n-te zyklotomische Polynom. Es wird gewählt, weil es über Z irreduzibel ist, dem Ring R_q gute algebraische Eigenschaften verleiht und die Number Theoretic Transform (NTT) für effiziente Multiplikationen ermöglicht. Zyklotomische Ringe sind umfassend untersucht und gelten als sicher.

Bei Ring-LWE ist das Geheimnis s ein Polynom in R_q, und die Stichproben haben die Form (a, b = a*s + e), wobei a ein gleichverteiltes zufälliges Ringelements und e ein kleines Fehlerpolynom ist. Der Angreifer sieht viele solcher Stichproben und muss s wiederherstellen oder sie von einer Gleichverteilung unterscheiden. Die Schwierigkeit beruht auf der Ring-LWE-Annahme, für die es eine Reduktion von Worst-Case-Problemen auf idealen Gittern gibt.

Ring-LWE ist für einen Angreifer schwieriger, bringt aber auch eine etwas andere Sicherheitsreduktion als einfaches LWE mit sich. Die Reduktion geht von Worst-Case-Problemen auf idealen Gittern (ideal-SVP) aus, nicht von beliebigen Gittern. Die zusätzliche Struktur idealer Gitter könnte sie prinzipiell leichter als allgemeine Gitter machen, und dies ist ein aktives Forschungsgebiet. Es ist kein praktischer Angriff bekannt, der diese Struktur ausnutzt.

Module-LWE (M-LWE) verallgemeinert sowohl LWE als auch Ring-LWE, indem es mit einer k x k-Matrix aus Ringelementen statt mit einem einzelnen Ringelements oder einer großen Ganzzahlenmatrix arbeitet. Für k = 1 ergibt sich Ring-LWE; mit wachsendem k nähert sich das Verfahren dem Standard-LWE an. Dieser einstellbare Parameter k ermöglicht einen Ausgleich zwischen dem Vertrauen in die Sicherheit und der Leistung.

CRYSTALS-Kyber, jetzt ML-KEM (FIPS 203), basiert auf Module-LWE mit einer Rang-k-Matrix über R_q. Der Parameter k bestimmt direkt die Sicherheitsstufe: k=2 zielt auf 128-Bit-Sicherheit (ML-KEM-512), k=3 auf 192 Bit (ML-KEM-768) und k=4 auf 256 Bit (ML-KEM-1024). Die Modulstruktur ermöglicht eine einheitliche Codebasis, deren Sicherheitsniveau durch Änderung von k skaliert werden kann.

Die Polynom-Multiplikation in R_q = Z_q[X]/(X^n + 1) ist der Leistungsengpass. Die Number Theoretic Transform (NTT) ist eine diskrete Fourier-Transformation über Z_q, die Polynome in eine Auswertungsdarstellung überführt, in der die Multiplikation punktweise erfolgt. Wenn q so gewählt wird, dass die NTT anwendbar ist, benötigt die Polynom-Multiplikation O(n log n) statt O(n^2) Zeit. Dies ist eine entscheidende Optimierung in ML-KEM und ML-DSA.

Die NTT setzt voraus, dass q eine Primzahl mit q = 1 mod 2n ist, wodurch sichergestellt wird, dass Z_q eine primitive 2n-te Einheitswurzel enthält. Für ML-KEM mit n = 256 erfüllt q = 3329 diese Anforderung. Die NTT über Z_3329 ist auf moderner Hardware mit SIMD-Instruktionen äußerst schnell und ermöglicht Tausende von ML-KEM-Operationen pro Sekunde auf handelsüblichen CPUs.

Ring-LWE und Module-LWE reduzieren die Schlüssellängen im Vergleich zu Standard-LWE drastisch. Ein öffentlicher Schlüssel für Standard-LWE mit 128-Bit-Sicherheit kann 1 MB groß sein; Ring-LWE reduziert diese Größe auf etwa 800 Byte, und Module-LWE (ML-KEM-768) erreicht mit 192-Bit-Post-Quanten-Sicherheit einen öffentlichen Schlüssel von 1184 Byte. Diese Kompaktheit macht Gitterverfahren für TLS und eingebettete Systeme praktisch einsetzbar.

Einige Kryptografen befürchten, dass die zusätzliche algebraische Struktur von Kreisteilungsringen Angriffe ermöglichen könnte, die auf gewöhnliches LWE nicht anwendbar sind. Im Jahr 2024 veröffentlichten Elias Rokicki und seine Mitautoren eine Analyse des 2n-ten Kreisteilungspolynoms. Sie fanden keine praktisch ausnutzbaren Schwachstellen, betonten aber die Bedeutung einer kontinuierlichen Überprüfung. Im NIST-PQC-Prozess wurde dieses Risiko berücksichtigt, und man entschied sich teilweise deshalb für Module-LWE, um die Abhängigkeit von einer einzelnen Ringstruktur zu verringern.

Neben Kyber bildet Ring-LWE die Grundlage für CRYSTALS-Dilithium (ML-DSA), das von NIST standardisierte Signaturverfahren. Die SEAL-Bibliothek von Microsoft ermöglicht homomorphe Verschlüsselung mittels Ring-LWE. Googles Tink-Kryptografiebibliothek unterstützt ML-KEM. Ring-LWE hat sich dank des NIST-Standardisierungsprozesses in bemerkenswert kurzer Zeit von einer theoretischen Konstruktion zu einer in der Praxis eingesetzten Technologie entwickelt.

Was ist der wichtigste Vorteil von Ring-LWE gegenüber gewöhnlichem LWE?

Ring-LWE überführt LWE in den Polynomring R_q = Z_q[X]/(X^n+1), wodurch sich die Schlüssellängen drastisch reduzieren und eine schnelle NTT-basierte Arithmetik möglich wird. Module-LWE verallgemeinert dieses Konzept mit einer Rang-k-Struktur und bildet die Grundlage für ML-KEM (FIPS 203) und ML-DSA (FIPS 204). Die NTT-freundliche Primzahl q = 3329 ermöglicht eine effiziente Implementierung. Die Sicherheit beruht auf der Schwierigkeit von Problemen auf Ideal- und Modulgittern.