Predicting Module-Lattice Reduction

Technische Samenvatting: Voorspellen van Module-Lattice Reductie

Probleemstelling
Het artikel behandelt een cruciale vraag in de cryptanalyse van module-lattice-gebaseerde cryptografische schema's (zoals de NIST-standaarden ML-KEM, ML-DSA en FN-DSA): Is module-lattice reductie (specifiek module-BKZ) efficiënter of minder efficiënt dan ongestructureerde lattice reductie (BKZ) wanneer beide worden gegeven met dezelfde Shortest Vector Problem (SVP) oracle?

Hoewel fundamentele theoretische werken de existentie van module-varianten van LLL en blok-reductie algoritmen hebben vastgesteld, richtten zij zich op de worst-case asymptotische gedrag. Een specifieke zorg, gehighlight als "Q8" in de Kyber NIST-indiening, stelt dat de algebraïsche structuur van module-lattices over cyclotome velden een versnelling zou kunnen mogelijk maken (bijv. een factor van $d$ naar $d^2$) of omgekeerd de kwaliteit van de gereduceerde basis kan verslechteren ten opzichte van ongestructureerde BKZ. Het artikel beoogt een concrete, average-case analyse te leveren om te beantwoorden of module-BKZ een winst of een verlies oplevert in termen van de vereiste blokgrootte $\beta$ om een specifieke basiskwaliteit (helling) te bereiken.

Methodologie
De auteurs maken gebruik van een heuristische analyse ondersteund door uitgebreide experimenten om de "helling" van het basisprofiel te voorspellen na het uitvoeren van module-BKZ. De helling wordt gedefinieerd als de snelheid van verval in de logaritmische normen van de Gram-Schmidt orthogonaliserende vectoren.

1. Experimentele Implementatie: De auteurs hebben de eerste open-source implementatie van module-BKZ voor cyclotome velden (tot geleider 16) ontwikkeld, gebruikmakend van de bestaande bibliotheken fplll en G6K. Zij hebben technische uitdagingen aangepakt met betrekking tot het behoud van de module-structuur tijdens de grootte-reductie (size reduction) en het gebruik van een "cyclische embedding" om ervoor te zorgen dat de trace-inproduct compatibel is met standaard integer lattice reductie bibliotheken.
2. Theoretische Modellering (Module-Lattice GSA): Zij breiden de Geometric Series Assumption (GSA), die veel wordt gebruikt voor ongestructureerde BKZ, uit naar module-lattices. Dit houdt in dat zij het verwachte $K$-profiel (gemiddeld over de graad $d$ van het getalsveld) van een gereduceerde basis modelleren.
3. Decompositie van de Helling: De voorspelde helling van module-BKZ wordt gedecomponeerd in vier afzonderlijke termen ($t_1$ tot $t_4$) die de afwijking van ongestructureerde BKZ drijven:
   • $t_1$ (Gaussian Heuristic): De verwachte lengte van de kortste vector in een willekeurige module-lattice, aangepast voor het aantal eenheden van de wortels van eenheid ($\mu_K$).
   • $t_2$ (Discriminant Gap): Een term afhankelijk van de discriminant $\Delta_K$ van het getalsveld $K$.
   • $t_3$ (Skewness Gap): Meet de afwijking van de algebraïsche norm van de vector van zijn Euclidische norm (de scheefheid/skewness van de vector over de embeddings).
   • $t_4$ (Index Gap): Houdt rekening met de index van het ideaal gegenereerd door de kortste vector binnen de module.
4. Asymptotische Analyse: De auteurs leiden een asymptotische formule af voor de "equivalente blokgrootte" $\beta_{eq}$ die vereist is voor module-BKZ om de helling van ongestructureerde BKZ met blokgrootte $\beta$ te evenaren.

Belangrijkste Bijdragen en Resultaten

• Kwantitatieve Voorspelling van de Helling: Het artikel biedt een concrete formule die de helling van module-BKZ voorspelt als een functie van de blokgrootte $\beta$, de veldgraad $d$, en de velddiscriminant $\Delta_K$.
• De Discriminant als Drijver: De analyse identificeert de discriminant $\Delta_K$ als de primaire grootheid die het prestatieverschil bepaalt. Specifiek bepaalt de term $\ln(|\Delta_K|/d^d)$ of module-BKZ winst of verlies boekt in efficiëntie.
• Asymptotische Blokgrootte Winst/Verlies: De auteurs leiden de volgende asymptotische relatie af voor de equivalente blokgrootte $\beta_{eq}$:
  $$\beta_{eq} \approx \beta + \ln\left(\frac{|\Delta_K|}{d^d}\right) \frac{\beta}{d \ln \beta} + (d - 1)$$
  • Power-of-Two Cyclotome Velden: Voor velden waar de geleider een macht van twee is (relevant voor huidige NIST-standaarden), geldt $|\Delta_K| = d^d$. Bijgevolg verdwijnt de logaritmische term, en wordt de kosten gedomineerd door de lineaire term $d-1$. Dit impliceert dat module-BKZ een blokgrootte vereist die ongeveer $d-1$ groter is om dezelfde helling te bereiken als ongestructureerde BKZ. Dit bevestigt en kwantificeert de zorg die werd geuit in Kyber's Q8, wat wijst op een lichte prestatie-straf in plaats van een versnelling.
  • Andere Cyclotome Velden: Voor velden met oneven priemfactoren in hun geleider (bijv. geleiders van de vorm $2^i \cdot 3^j$), geldt $|\Delta_K| < d^d$. In deze gevallen is de logaritmische term negatief, wat resulteert in een sublineaire winst in de vereiste blokgrootte ($\Theta(\beta / \ln \beta)$). Dit vertaalt zich in een subexponentiële versnelling in de aanvalscomplexiteit.
• Experimentele Validatie: De experimentele gegevens van de auteurs over diverse cyclotome velden ($\mathbb{Q}(\omega_3), \mathbb{Q}(\omega_4), \mathbb{Q}(\omega_{15}), \mathbb{Q}(\omega_{16})$) komen goed overeen met hun voorspellingen. De data bevestigen dat $\mathbb{Q}(\omega_3)$ en $\mathbb{Q}(\omega_{15})$ vlakkere profielen (betere reductie) vertonen vergeleken met de ongestructureerde baseline, terwijl $\mathbb{Q}(\omega_{16})$ (power-of-two) een slechter profiel laat zien.

Betekenis en Claims
Het artikel claimt het eerste werk te zijn dat een concrete, average-case analyse van module-BKZ biedt, waarbij verder wordt gekeken dan worst-case theoretische grenzen. De significantie ligt in:

1. Het Oplossen van Q8: Het adresseert direct de openstaande vraag over de efficiëntie van module-BKZ op power-of-two cyclotome velden, en concludeert dat voor deze specifieke velden de module-structuur geen versnelling biedt ten opzichte van ongestructureerde BKZ; het brengt zelfs een kleine overhead met zich mee (vereist een grotere blokgrootte).
2. Identificatie van Alternatieve Constructies: Het benadrukt dat module-lattice schema's die gebruikmaken van geleiders met kleine oneven priemfactoren (bijv. 3, 5) aanzienlijk zwakker kunnen zijn dan voorheen gedacht, aangezien de algebraïsche structuur een subexponentiële versnelling biedt voor lattice reductie aanvallen.
3. Praktische Hulpmiddelen: Door de eerste open-source implementatie van module-BKZ te bieden, stellen de auteurs verdere experimentatie en veiligheidsinschatting voor module-lattice schema's mogelijk.

De auteurs blijven bescheiden over hun claims en merken op dat hun analyse steunt op heuristieken (zoals de Geometric Series Assumption aangepast voor modules) en dat er nog hiaten zijn in het modelleren van "head and tail" fenomenen en de convergentiesnelheid van het algoritme. Zij stellen expliciet dat hun resultaten nog geen precieze kosten bieden voor specifieke aanvallen, maar eerder een voorspellend kader vormen voor de helling van de gereduceerde basis.