An alternative approach towards attacks against fully-split PLWE instances

Sintesi Tecnica: Un approccio alternativo agli attacchi contro istanze PLWE completamente scomponibili

Definizione del Problema
Il problema del Polynomial Learning With Errors (PLWE) è un pilastro della crittografia post-quantistica, spesso preferito rispetto al Ring-LWE per le sue proprietà algebriche strutturate che ne favoriscono l'efficienza. Tuttavia, questa struttura introduce potenziali vulnerabilità. Lavori precedenti, in particolare [5, 6] e generalizzati in [2], hanno introdotto gli "attacchi basati sulle radici" (root-based attacks) che sfruttano l'esistenza di specifici fattori polinomiali (noti come fattori $n$-ideali, $x^n - a$) su campi finiti. Questi attacchi utilizzano omomorfismi di valutazione e operatori di traccia per distinguere i campioni PLWE da distribuzioni uniformi.

Sebbene [2] abbia generalizzato questi attacchi a polinomi che si scompongono in estensioni di campo, una questione critica rimaneva aperta: un attaccante potrebbe aggirare la mancanza di fattori vulnerabili in un'istanza PLWE "sicura" mappandola tramite un isomorfismo d'anello a un'istanza "vulnerabile" (una dotata di idonei fattori $n$-ideali), eseguendo l'attacco lì e inferendo la sicurezza dell'istanza originale? Questo articolo investiga se una strategia di migrazione tramite isomorfismi offra un vantaggio significativo contro le istanze PLWE completamente scomponibili.

Metodologia
Gli autori impiegano un approccio algebrico rigoroso per analizzare la fattibilità del trasferimento di campioni PLWE tra diversi anelli polinomiali. La metodologia procede in due fasi principali:

1. Generalizzazione della scomposizione arbitraria: Il documento esplora prima l'estensione degli attacchi basati sulle radici a polinomi privi di fattori $n$-ideali. Utilizzando il Lemma 1, gli autori dimostrano che gli operatori di traccia possono essere definiti su arbitrari fattori irriducibili. Tuttavia, mostrano che la probabilità di successo di tali attacchi dipende fortemente dal numero di coefficienti con valore zero nel fattore, che è tipicamente basso per polinomi arbitrari, rendendo l'attacco impraticabile nel caso generale.

2. Analisi dell'isomorfismo in contesti completamente scomponibili: Il cuore del lavoro si concentra sull' "approccio per isomorfismo". Gli autori considerano due polinomi, $f(x)$ e $g(x)$, entrambi di grado $N$ e irriducibili su $\mathbb{Z}[x]$, che condividono la stessa "struttura di scomposizione" su $\mathbb{F}_q$ (ovvero, si decompongono in fattori irriducibili con gli stessi gradi).

   • Costruzione: Utilizzando il Teorema Cinese del Resto, costruiscono un isomorfismo esplicito $\psi$ tra gli anelli $R_q = \mathbb{F}_q[x]/(f(x))$ e $R'_q = \mathbb{F}_q[x]/(g(x))$. Nel caso completamente scomponibile (dove entrambi i polinomi si decompongono completamente in termini lineari), questo isomorfismo è rappresentato dal prodotto di matrici di Vandermonde: $\psi = V_g^{-1} \cdot V_f$.
   • Analisi della distorsione: Gli autori analizzano l'effetto dell'applicazione di questo isomorfismo ai campioni PLWE seguito da una valutazione in una radice $\beta$ di $g(x)$. Dimostrano che la valutazione risultante è matematicamente equivalente alla valutazione del campione originale in una corrispondente radice $\alpha$ di $f(x)$.
   • Dimostrazione di unicità: Una parte significativa della metodologia riguarda la dimostrazione che qualsiasi isomorfismo d'anello tra tali anelli polinomiali completamente scomponibili deve assumere questa specifica forma (composizione di omomorfismi di valutazione e dell'isomorfismo costruito). Ciò è stabilito attraverso i Lemmi 2, 3 e 4, e il Teorema 1.

Contributi Chiave

• Prova formale dell'invarianza dell'isomorfismo: Il documento fornisce una prova formale che, per le istanze PLWE completamente scomponibili, qualsiasi tentativo di migrare i campioni verso un contesto vulnerabile tramite un isomorfismo d'anello non produce nuove vulnerabilità. Il rumore (errore) introdotto dall'isomorfismo distorce i campioni in modo tale che le condizioni di distinguibilità risultanti siano identiche a quelle dell'istanza originale.
• Caratterizzazione degli isomorfismi d'anello: Gli autori caratterizzano l'insieme completo degli isomorfismi tra anelli polinomiali completamente scomponibili, mostrando che essi sono unicamente determinati dalla mappatura delle radici. Ciò dimostra che non esiste un isomorfismo "nascosto" in grado di aggirare la distorsione del rumore.
• Estensione alla scomposizione arbitraria: Il lavoro chiarisce che, sebbene gli attacchi basati sulle radici possano teoricamente essere applicati a polinomi privi di fattori $n$-ideali, la mancanza di vincoli strutturali (specificamente il numero di coefficienti zero) limita severamente la loro probabilità di successo, chiudendo di fatto la porta a questa generalizzazione come minaccia pratica.

Risultati

• Distorsione del rumore: L'applicazione di un isomorfismo $\psi$ seguito da una valutazione in una radice $\beta$ di $g(x)$ risulta nell'espressione $b(\beta) = \sum a_j \alpha^j$, dove $\alpha$ è la corrispondente radice di $f(x)$. Ciò dimostra che l'attacco sul contesto trasformato è matematicamente identico all'attacco sul contesto originale.
• Fallimento della strategia di migrazione: L'analisi conferma che se un attacco basato sulle radici fallisce sull'istanza PLWE originale (a causa dell'alto rumore o della mancanza di distinguibilità), fallirà anche su qualsiasi istanza isomorfa. L'isomorfismo non "pulisce" il rumore; piuttosto, preserva la difficoltà intrinseca del problema.
• Analisi di radici specifiche: Il documento analizza casi specifici in cui la radice di valutazione $\beta$ è $0$, $1$ o una radice arbitraria. In tutti i casi, la valutazione risultante si riduce alla valutazione del polinomio originale in una corrispondente radice, confermando che non si ottiene alcun vantaggio.

Significatività
Il documento conclude che l'intuizione riguardante la sicurezza delle istanze PLWE completamente scomponibili è corretta: se gli attacchi basati sulle radici non hanno successo contro un'iniziale istanza PLWE, rimarranno comunque senza successo anche se i campioni vengono trasferiti in un contesto PLWE potenzialmente più debole tramite isomorfismi d'anello.

Questo risultato fornisce una fonte di fiducia per la sicurezza delle istanze PLWE completamente scomponibili, che sono comuni nelle costruzioni crittografiche per la loro efficienza (ad esempio, nelle Trasformate di Numero Teorico - NTT). Il lavoro esclude efficacementamente la "migrazione per isomorfismo" come un vettore praticabile per generare nuovi attacchi contro queste specifiche istanze. Gli autori osservano che, sebbene questa analisi sia specifica per i polinomi completamente scomponibili, essa copre la stragrande maggioranza delle istanze PLLE crittograficamente rilevanti. Il documento non pretende di risolvere la sicurezza delle istanze PLWE non completamente scomponibili o altri vettori di attacco (come gli attacchi all'ideale di Stickelberger menzionati nell'introduzione), ma piuttosto consolida la comprensità degli attacchi basati sulle radici all'interno del dominio dei completamente scomponibili.