Improving ML Attacks on LWE with Data Repetition and Stepwise Regression

1. Problemstellung: LWE und ML-Angriffe

Das Learning with Errors (LWE)-Problem ist ein fundamentales mathematisches Problem, das die Sicherheit vieler postquantenkryptografischer (PQC) Systeme garantiert. Es besteht darin, einen geheimen Vektor $s$ zu finden, gegeben noisy Punktprodukte $(a_i, b_i = a_i \cdot s + \epsilon_i \mod q)$.

Bisherige Machine-Learning (ML)-Angriffe (wie SALSA, PICANTE, VERDE) auf LWE mit kleinen oder dünnbesetzten (sparse) Geheimnissen stießen an eine fundamentale Grenze:

• Die „Cruel Region": Nach einer Vorverarbeitung mittels Gitterreduktion (BKZ) bleibt ein Teil des Geheimvektors (die ersten $c$ Koordinaten) unreduziert. Diese werden als „cruel bits" bezeichnet. Der Rest (die „cool bits") wird stark reduziert und ist leichter zu lösen.
• Die Limitierung: Vorherige ML-Modelle konnten erfolgreich nur Geheimnisse mit maximal 3 aktiven „cruel bits" (Hamming-Gewicht im unreduzierten Bereich) rekonstruieren. Sobald die Anzahl der unreduzierten Bits höher war, scheiterten die Modelle, da sie Schwierigkeiten hatten, modulare Additionen zu lernen, wenn die Summe mehrfach den Modul $q$ übersteigt.

Das Ziel dieses Papers ist es, diese Grenze zu durchbrechen und ML-Angriffe so zu verbessern, dass sie Geheimnisse mit deutlich mehr „cruel bits" (bis zu 8) und höherem Gesamt-Hamming-Gewicht rekonstruieren können.

2. Methodik

Die Autoren führen drei wesentliche methodische Neuerungen ein:

A. Große Datensätze und Datenwiederholung (Data Repetition)

Anstatt nur große Mengen an einzigartigen Beispielen zu verwenden, trainieren die Modelle auf Datensätzen, in denen Beispiele mehrfach wiederholt werden.

• Hypothese: Basierend auf früheren Arbeiten (Charton & Kempe, Saxena et al.) zeigt sich, dass Transformer-Modelle modulare Operationen besser lernen, wenn sie dieselben Beispiele oft wiederholt sehen, auch wenn der Gesamtdatensatz kleiner ist.
• Umsetzung: Es wurden synthetische und BKZ-reduzierte Datensätze mit bis zu 400 Millionen Beispielen generiert, wobei Wiederholungsfaktoren von 1x bis 50x getestet wurden.

B. Stepwise Regression für „Cool Bits"

Nachdem die „cruel bits" durch das ML-Modell erraten wurden, müssen die verbleibenden „cool bits" rekonstruiert werden.

• Kritik an Linearer Regression: Bisherige Methoden verwendeten lineare Regression. Die Autoren argumentieren, dass dies suboptimal ist, da:
  1. Die Eingabemerkmale (Spalten von $A$) unkorreliert sind, was die Inversion der Kovarianzmatrix bei linearer Regression fehleranfällig macht.
  2. Lineare Regression das modulare „Wrap-around" (Überlauf bei $q$) ignoriert und nicht-sparsame Lösungen begünstigt.
• Neuer Ansatz (Stepwise Regression): Sie führen eine schrittweise Regression ein, die Null-Bits iterativ identifiziert und eliminiert.
  • Dual Stepwise Regression: Sobald die Null-Bits entfernt sind und die restlichen Bits hauptsächlich Einsen sind, wird das Problem dualisiert (Flip der Bits), um die verbleibenden Einsen effizient zu finden. Dies nutzt die Sparsamkeit des Geheimnisses optimal aus.

C. Modellarchitektur und Vorverarbeitung

• Architektur: Ein Encoder-only Transformer mit 4 Layern.
• Embeddings: Einführung einer speziellen „Cool/Cruel"-Embedding-Schicht, die dem Modell signalisiert, ob eine Position im unreduzierten oder reduzierten Bereich liegt. Dies verbessert die Rekonstruktionsrate der „cruel bits" signifikant.
• Daten: Nutzung von BKZ-reduzierten Daten sowie synthetischen Daten (die gleiche Varianz wie reduzierte Daten aufweisen), um die Skalierungsgesetze zu untersuchen.

3. Wichtige Beiträge

1. Überwindung der 3-Bit-Grenze: Die Autoren zeigen, dass durch große Trainingsmengen und Wiederholung Geheimnisse mit bis zu 8 „cruel bits" erfolgreich rekonstruiert werden können.
2. Einführung der Stepwise Regression: Ein neuer Algorithmus zur Rekonstruktion der „cool bits", der lineare Regression in diesem spezifischen Kontext deutlich übertrifft.
3. Skalierungsgesetze (Scaling Laws): Die Autoren definieren erstmals ein empirisches Skalierungsgesetz für LWE-Angriffe. Sie zeigen eine Potenzgesetz-Beziehung zwischen der Anzahl der benötigten Versuche ($A$), der Datenmenge ($D$) und der Wiederholung ($R$):
   $$\ln(A \cdot R) = C_R - \alpha_R \ln(D)$$
   Dabei ist $\alpha_R$ für höhere Wiederholungsraten größer, was bedeutet, dass Wiederholung die Skalierungseffizienz drastisch verbessert.
4. Synthetische Daten: Sie demonstrieren, dass Modelle, die auf synthetischen Daten trainiert werden (die die statistischen Eigenschaften von BKZ-reduzierten Daten nachahmen), genauso gut performen wie solche auf echten reduzierten Daten. Dies ermöglicht kostengünstige Experimente ohne teure BKZ-Berechnungen.

4. Ergebnisse

Die Ergebnisse wurden in vier verschiedenen LWE-Parametereinstellungen ($n=256/512$, verschiedene Moduli $q$) getestet und mit dem aktuellen State-of-the-Art (VERDE, Cool & Cruel) verglichen.

• Maximales Hamming-Gewicht:
  • Bei $n=256, \log_2 q = 20$: Rekonstruktion von Geheimnissen mit h=70 (8 cruel bits), im Vergleich zu h=33 bei VERDE.
  • Bei $n=512, \log_2 q = 41$: Rekonstruktion von h=75 (7 cruel bits), im Vergleich zu h=63 bei VERDE.
• Rekonstruktionsrate (Erwartungswert):
  • Für $n=256, \log_2 q = 20$ und $h=33$: VERDE erreicht eine Erfolgsrate von 33%, während die neue Methode 98% erreicht.
  • Für $n=512, \log_2 q = 41$ und $h=63$: VERDE erreicht 15%, die neue Methode 91%.
• Ressourceneffizienz: Die Methode funktioniert auch mit synthetischen Daten, was die Notwendigkeit teurer BKZ-Vorverarbeitung für das Training eliminiert.

5. Bedeutung und Fazit

Dieses Paper hat weitreichende Implikationen für die Sicherheit postquantenkryptografischer Systeme:

1. Schwächung von LWE-Varianten: Es zeigt, dass LWE-Systeme mit kleinen oder dünnbesetzten Geheimnissen (die oft für Effizienz in homomorpher Verschlüsselung verwendet werden) anfälliger sind als bisher angenommen. Die Annahme, dass ML-Angriffe auf 3 unreduzierte Bits begrenzt sind, ist widerlegt.
2. Neue Angriffsstrategie: Die Kombination aus Datenwiederholung und schrittweiser Regression bietet einen neuen, effektiven Weg, um LWE-Probleme zu lösen, der sowohl ML- als auch klassische nicht-ML-Angriffe (wie Cool & Cruel) bei vergleichbaren Budgets übertrifft.
3. Rolle von Skalierungsgesetzen: Die Arbeit etabliert ein Framework, um den Erfolg von ML-Angrissen auf kryptografische Probleme basierend auf Datenmenge und Modellgröße vorherzusagen.
4. Warnung an die Standardisierung: Da PQC-Systeme bald standardisiert werden, unterstreicht diese Forschung die Notwendigkeit, die Sicherheit von Systemen mit dünnbesetzten Geheimnissen kritisch zu hinterfragen und Sicherheitsmargen entsprechend anzupassen.

Zusammenfassend beweist die Arbeit, dass ML-Angriffe auf LWE durch strategische Datennutzung und verbesserte statistische Nachbearbeitung signifikant gestärkt werden können, was die Sicherheitsgrenzen für bestimmte PQC-Parameter neu definiert.