Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

Riepilogo Tecnico: Attacco Quantistico Probabilistico Polinomiale a Module-LWE su Ciclotomici di Potenza di 2

Enunciato del Problema
Il documento affronta la sicurezza degli schemi crittografici basati su Module Learning With Errors (Module-LWE), focalizzandosi specificamente su ML-KEM standardizzato dal NIST (precedentemente CRYSTALS-Kyber) e su schemi correlati basati su reticoli (Falcon, Hawk, NTRU) costruiti su anelli ciclotomici di potenza di 2 ($R = \mathbb{Z}[\zeta_{2^k}]$). Il problema centrale è il recupero delle chiavi segrete tramite il Problema del Vettore più Breve (SVP) su reticoli moduli. Mentre gli attacchi classici si basano su algoritmi di riduzione dei reticoli (ad es. BKZ) con complessità esponenziale, il documento indaga se un avversario quantistico possa sfruttare la struttura algebrica degli anelli ciclotomici per risolvere efficientemente il Problema dell'Ideale Principale (PIP) e il Problema del Generatore Breve (SGP).

Gli autori identificano due questioni critiche irrisolte nei lavori precedenti (in particolare l'attacco CDPR):

1. Il fattore di approssimazione raggiunto dall'attacco CDPR è sufficientemente piccolo per violare le chiavi segrete complete di ML-KEM (ovvero, è $\gamma < q/2$)?
2. La subroutine quantistica PIP sottostante raggiunge una complessità temporale polinomiale vera, senza sovraccarichi esponenziali nascosti o dipendenza dall'Ipotesi di Riemann Generalizzata (GRH)?

Metodologia
Il documento presenta una pipeline di attacco unificata a quattro fasi (Algoritmo 1) che integra i risultati delle Parti I–III della serie con un nuovo algoritmo quantistico polinomiale per il PIP (Parte IV).

1. Riduzione da Modulo a Ideale: L'attacco inizia riducendo l'istanza Module-LWE a un Problema dell'Ideale Principale. Utilizzando una decomposizione di Gram-Schmidt, la base del modulo viene trasformata in un prodotto di ideali principali. Gli autori dimostrano che la riduzione introduce solo un fattore costante $\alpha_d = O(1)$, indipendente dal rango del modulo $d$.
2. PIP a Torre Quantistica: Invece di risolvere il PIP nel campo completo $\mathbb{Q}(\zeta_{2^k})$ direttamente, gli autori propongono una strategia di "decomposizione a torre". Decompongono il campo in una catena di estensioni quadratiche: $\mathbb{Q} \subset \mathbb{Q}(\zeta_8) \subset \dots \subset \mathbb{Q}(\zeta_{2^k})$.
   • A ogni livello $L$, l'algoritmo risolve il PIP per l'estensione relativa utilizzando il Problema del Sottogruppo Nascosto Abeliano (HSP).
   • Crucialmente, il numero di nuovi generatori di unità a ogni livello cresce linearmente ($\Delta r_L = 2^{L-3}$), mantenendo la dimensione dell'istanza HSP polinomiale.
   • Questo approccio evita l'esplosione dei coefficienti intrinseca nelle rappresentazioni standard a base di potenza ed elimina la necessità della GRH, poiché è dimostrato che il numero di classi del sottocampo reale massimale è 1 per $k \le 12$.
3. Log-Unit CVP: Una volta trovato un generatore $g$ dell'ideale (che può essere esponenzialmente lungo), l'algoritmo calcola il suo embedding logaritmico. Risolve quindi il Problema del Vettore più Vicino (CVP) sul reticolo delle unità logaritmiche per trovare la discrepanza di unità $\epsilon$ tale che $g = g_0 \epsilon$, dove $g_0$ è il generatore breve.
   • Gli autori utilizzano l'algoritmo del piano più vicino di Babai. Dimostrano che per generatori di anelli brevi, il vettore target giace all'interno del "raggio di cattura" del reticolo, permettendo all'algoritmo di Babai di recuperare esattamente la discrepanza di unità.
4. Recupero del Generatore Breve: L'unità $\epsilon$ viene ricostruita dalla soluzione CVP, e il generatore breve viene recuperato come $g_0 = g \cdot \epsilon^{-1}$.

Contributi Chiave

• PIP Quantistico in Tempo Polinomiale: Il documento fornisce la prima costruzione di un algoritmo quantistico in tempo polinomiale per il PIP su anelli ciclotomici di potenza di 2. La complessità è di $O(n^3 \log^2 n)$ porte quantistiche e $O(n^2 \log n)$ qubit, dove $n$ è il grado dell'anello. Questo rimuove il sovraccarico esponenziale precedentemente associato all'algoritmo Biasse-Song.
• Analisi del Fattore di Approssimazione Stretto: Gli autori derivano un fattore di approssimazione esatto $\gamma = \alpha_d \cdot \exp(\sigma_d \sqrt{2 \ln n})$. Dimostrano che la varianza $\sigma_d$ dell'embedding logaritmico è $O(1)$ e indipendente dal modulo $q$.
• Verifica del Numero di Classi: Il lavoro si basa sulla dimostrazione (dalla Parte I) che il numero di classi del sottocampo reale massimale è banale ($h^+_k = 1$) per tutti i $k \le 12$, garantendo che ogni ideale sia principale.
• Estensione a Più Schemi: Il framework viene esteso oltre ML-KEM per analizzare varianti di Falcon, Hawk e NTRU su ciclotomici di potenza di 2, dimostrando che le stesse debolezze algebriche si applicano.

Risultati
Gli autori forniscono stime di sicurezza concrete per set di parametri standardizzati:

• ML-KEM-1024: L'attacco raggiunge un fattore di approssimazione mediano $\gamma_{med} \approx 21$ e un fattore al 99° percentile $\gamma_{99\%} \approx 103$. Entrambi i valori sono significativamente al di sotto della soglia di sicurezza $q/2 = 1665$. La probabilità di successo è stimata $\ge 0.99$ per $d \le 3$ e $\ge 0.90$ per $d=4$, con una probabilità di fallimento riducibile a $< 10^{-6}$ tramite ripetizione.
• Stime delle Risorse: Per ML-KEM-1024 ($n=256$), l'attacco richiede circa $2^{27}$ porte logiche e $1.4 \times 10^6$ qubit fisici (assumendo un codice di superficie con distanza 30).
• Altri Schemi:
  • Falcon: L'attacco viola Falcon-512 e Falcon-1024 con margini di $72\times$ e $63\times$ rispettivamente.
  • Hawk: L'attacco viola Hawk-512 e Hawk-1024. Hawk-256 è violato condizionalmente; sebbene il limite formale al 99% superi la soglia, le simulazioni empiriche mostrano un tasso di successo del 99,99%.
  • NTRU: L'attacco si applica alle varianti NTRU-HPS e NTRU-HRSS su anelli ciclotomici di potenza di 2, raggiungendo margini che variano da $11\times$ a $45\times$.

Significato e Affermazioni
Il documento afferma di risolvere le questioni aperte riguardanti l'attacco CDPR dimostrando che:

1. Il fattore di approssimazione è abbastanza piccolo da violare tutti i set di parametri standardizzati di ML-KEM, Falcon, Hawk e NTRU su anelli ciclotomici di potenza di 2 sotto un attacco quantistico.
2. Il PIP può essere risolto in tempo polinomiale vero ($O(n^3 \log^2 n)$) senza fattori esponenziali nascosti o dipendenza da congetture numeriche non dimostrate come la GRH.
3. La struttura algebrica degli anelli ciclotomici di potenza di 2 permette a un avversario quantistico di ridurre il fattore di approssimazione da super-polinomiale ($\approx 2^{54}$ nelle stime precedenti) a sub-polinomiale ($\approx 2^{21}$), violando efficacemente le ipotesi di sicurezza di questi candidati post-quantistici.

Gli autori notano che, sebbene l'attacco sia probabilistico, la probabilità di fallimento è bassa e può essere mitigata da ripetizioni indipendenti. Sottolineano che i risultati dipendono dalle proprietà algebriche specifiche degli anelli ciclotomici di potenza di 2 e dalla banalità del numero di classi per $k \le 12$.