Improving ML Attacks on LWE with Data Repetition and Stepwise Regression

Probleemstelling

Het Learning With Errors (LWE) probleem is een fundamenteel wiskundig probleem dat de basis vormt voor veel post-kwantum cryptografische systemen (PQC). Het doel is om een geheim vector $s$ te vinden uit een reeks verstoarde inproducten $(a_i, b_i = a_i \cdot s + \epsilon_i \mod q)$.

Hoewel LWE algemeen als veilig wordt beschouwd, zijn er kwetsbaarheden bij specifieke varianten met kleine of schaarse geheimen (bijv. binaire of ternaire geheimen met een lage Hamming-gewicht). Eerdere machine learning (ML) aanvallen, zoals SALSA, hebben aangetoond dat transformer-modellen deze geheimen kunnen herstellen, maar slechts tot een bepaalde limiet.

• De "Cruel" vs. "Cool" Region: Na voorverwerking met lattice-reductie (BKZ) worden de laatste coördinaten van het geheim (de "cool bits") sterk gereduceerd en makkelijk te recoveren. De eerste coördinaten (de "cruel bits") blijven echter grotendeels ongereduceerd.
• De Limiet: Bestaande ML-aanvallen faalden wanneer het geheim meer dan 3 "cruel bits" had. De modellen hadden moeite om de modulaire optelling te leren wanneer de som van het inproduct te groot werd (veelvoudig van de modulus $q$), wat leidde tot een "wrap-around" effect.

Methodologie

De auteurs introduceren een verbeterde aanpak die drie kerncomponenten combineert om deze limiet te doorbreken:

1. Grote Trainingssets en Data-repetitie:

   • In plaats van unieke voorbeelden te gebruiken, trainen ze modellen op zeer grote datasets (tot 400 miljoen samples) met herhaalde voorbeelden.
   • Gebaseerd op eerdere bevindingen (Charton & Kempe, 2024; Saxena et al., 2025) tonen ze aan dat het herhalen van data de leerbaarheid van modulaire operaties aanzienlijk verbetert, zelfs bij complexe scenario's.
   • Ze genereren zowel BKZ-gereduceerde data als synthetische data (met dezelfde statistische eigenschappen) om de schaalbaarheid te testen zonder de hoge rekentijd van BKZ-reductie.

2. Verbeterde Model Architectuur:

   • Ze gebruiken een Encoder-only Transformer met 4 lagen.
   • Een belangrijke innovatie is de toevoeging van een binair posities-embedding dat aangeeft of een coördinaat in de "cruel" of "cool" regio zit. Dit helpt het model om de verschillende moeilijkheidsgraden van de bits te onderscheiden.
   • Ze gebruiken angular embeddings voor de invoercoördinaten om modulaire rekenkunde beter te modelleren.

3. Stapsgewijze Regressie (Stepwise Regression) voor "Cool Bits":

   • Eerdere methoden gebruikten lineaire regressie om de "cool bits" te recoveren nadat de "cruel bits" bekend waren. Dit faalde vaak omdat lineaire regressie de modulaire aard van het probleem negeert en fouten cumuleert.
   • De auteurs introduceren stepwise regression:
     • Ze elimineren iteratief de bits met de kleinste bijdrage (verondersteld als 0) en passen het model aan.
     • Ze introduceren een dual stepwise regression: zodra de resterende bits meer enen dan nullen zijn, "flippen" ze de bits en herhalen ze het proces.
   • Deze methode benut de sparsiteit van het geheim en minimaliseert fouten door modulaire wrap-arounds te vermijden.

Belangrijkste Bijdragen

• Doorbreken van de "3 Cruel Bits" Barrière: De aanpak slaagt erin geheimen te recoveren met tot 8 "cruel bits", een significant improvement ten opzichte van de eerdere limiet van 3.
• Empirische Schaalwetten: De auteurs definiëren een empirische machtswet (power-law) die de relatie beschrijft tussen het aantal benodigde pogingen om een geheim te vinden, de datasetgrootte ($D$) en het herhalingsniveau ($R$). Ze tonen aan dat data-repetitie de schaalwet fundamenteel verandert en essentieel is voor succes.
• Synthetische Data Validatie: Ze bewijzen dat modellen getraind op synthetische data (gegenereerd zonder dure BKZ-reductie) dezelfde prestaties leveren als die op echte BKZ-gereduceerde data. Dit opent de deur voor goedkopere experimenten en pre-training.
• Verbeterde Recoveriesnelheid: Ze presenteren een nieuwe methode voor het recoveren van "cool bits" die superieur is aan lineaire regressie, vooral bij hoge Hamming-gewichten.

Resultaten

De auteurs testen hun methode op vier verschillende LWE-configuraties ($n=256/512$ en verschillende waarden voor $q$). De resultaten tonen een aanzienlijke verbetering ten opzichte van eerdere werken (zoals VERDE en Cool & Cruel):

• Maximale Hamming-gewichten:
  • Voor $n=256, \log_2 q = 20$: Recoveren van geheimen met $h=70$ (vs. $h=33$ bij VERDE) en 8 cruel bits.
  • Voor $n=512, \log_2 q = 41$: Recoveren van geheimen met $h=75$ (vs. $h=63$ bij VERDE) en 7 cruel bits.
• Betrouwbaarheid: Niet alleen kunnen ze zwaardere geheimen recoveren, maar de verwachte recoveriesnelheid ($E(h)$) is ook veel hoger. Voor $h=33$ recoveren ze 98% van de geheimen, terwijl eerdere methoden slechts 33% haalden.
• Data-efficiëntie: Met data-repetitie kunnen ze succesvol zijn met kleinere datasets. Bijvoorbeeld, voor $n=512$ met 20 miljoen unieke voorbeelden herhaald 10 keer, kunnen ze 4 cruel bits recoveren.

Significantie en Conclusie

Deze studie heeft belangrijke implicaties voor de veiligheid van post-kwantum cryptografie:

1. Veiligheidsbeoordeling: Het toont aan dat de limiet van ML-aanvallen op LWE niet vaststaat bij 3 cruel bits. Systemen die zijn ontworpen met de aanname dat ML-aanvallen beperkt zijn tot zeer schaarse geheimen, moeten mogelijk worden herzien.
2. Rol van Data: Het benadrukt dat de schaalbaarheid van ML-aanvallen sterk afhankelijk is van de hoeveelheid data en de strategie van herhaling, niet alleen van de modelgrootte.
3. Kosten-effectiviteit: Het gebruik van synthetische data en de stapsgewijze regressie maakt het mogelijk om zwaardere varianten van LWE te testen zonder de enorme rekentijd van lattice-reductie, wat de research naar kwetsbaarheden versnelt.

Kortom, de auteurs tonen aan dat ML-aanvallen op LWE met kleine en schaarse geheimen sterker zijn dan eerder gedacht, en bieden een roadmap voor het verder testen van de robustheid van toekomstige PQC-standaarden.