🔢 mathematics

Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

Questo articolo presenta un attacco di recupero della chiave in tempo polinomiale che rompe tutti i set di parametri proposti dello schema di cifratura Enhanced Gabidulin Matrix Codes (EGMC), combinando tecniche combinatorie e algebriche per recuperare una chiave segreta equivalente, riducendo così il livello di sicurezza dichiarato da 128 bit a soli 35 bit.

Autori originali: Thai Hung Le

Pubblicato 2026-08-05

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Thai Hung Le

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immaginate internet come una città enorme e frenetica dove tutti cercano di inviare messaggi segreti. Per mantenere questi messaggi al sicuro da occhi indiscreti, usiamo serrature digitali chiamate crittografia. Per molto tempo, gli scienziati hanno costruito queste serrature utilizzando enigmi matematici complessi che sono facili da creare ma incredibilmente difficili da risolvere senza la chiave. Recentemente, è stata proposta un'altra tipologia di serratura utilizzando un tipo speciale di matematica che coinvolge griglie di numeri e il "rango" (che è solo un modo elegante per misurare quanta informazione è effettivamente racchiusa nella griglia). I creatori di questa nuova serratura pensavano di aver aggiunto uno strato di "rumore" — come l'interferenza su una radio — per nascondere la vera forma della serratura, facendola apparire come un caos casuale a chiunque tentasse di scardinarla. Affermavano che questo nuovo design fosse così sicuro che persino un computer quantistico superveloce non avrebbe potuto violarlo, e promettevano che sarebbe stato minuscolo ed efficiente, perfetto per il futuro della comunicazione sicura.

Tuttavia, proprio come un trucco di magia che si basa su un particolare gioco di prestigio, questa nuova serratura aveva un difetto nascosto. Un ricercatore, Thai Hung Le, ha scoperto che il "rumore" non nascondeva la forma segreta così bene come tutti pensavano. Utilizzando un mix astuto di tentativi ed errori e lavoro investigativo algebrico, il ricercatore ha trovato un modo per scrostare gli strati di interferenza e rivelare la struttura originale e nascosta sottostante. È come se qualcuno avesse costruito una casa di carte con un progetto segreto, l'avesse coperta con la nebbia, e poi si fosse reso conto che, se si guardasse la nebbia dall'angolazione giusta, il progetto sarebbe ancora debolmente visibile. Questa scoperta è un grande evento perché significa che le nuove serrature non sono sicure come pubblicizzato, e le persone che hanno progettato i loro blueprint devono ripensare i loro progetti prima di iniziare a usarli per proteggere i nostri dati.

La Grande Scoperta del Paper

In questo articolo, Thai Hung Le presenta un nuovo modo per violare gli schemi di crittografia "Enhanced Gabidulin Matrix Code" (EGMC). Questi schemi sono stati introdotti di recente come un modo per creare chiavi di crittografia molto piccole ed efficienti che potessero sopravvivere agli attacchi di futuri computer quantistici. La sicurezza di questi schemi si basava sull'idea che, se si prendeva una griglia speciale e strutturata di numeri e si aggiungevano righe e colonne casuali (il "rumore"), sarebbe diventato impossibile distinguere tra il codice reale e un caos completamente casuale.

L'autore dimostra che questa ipotesi è errata. Invece di cercare di forzare ogni possibile modo per rimuovere il rumore (il che richiederebbe un tempo infinito), il paper introduce un attacco "ibrido". Immaginate di cercare di trovare un motivo specifico in un enorme mosaico rimescolato. Il vecchio metodo consisteva nel indovinare la posizione di ogni singolo tassello. Questo nuovo metodo è più intelligente: indovina la posizione di una sola riga di tasselli e poi usa la matematica per capire istantaneamente dove devono trovarsi tutti gli altri tasselli.

Il paper dettaglia due modi principali per farlo:

Indovinare le Colonne: l'attaccante indovina come sono state rimescolate le colonne della griglia e poi usa l'algebra per risolvere come sono state rimescolate le righe.
Indovinare le Righe: l'attaccante indovina come sono state rimescolate le righe e poi risolve per le colonne.

Una volta che l'attaccante ha capito il rimescolamento, può rimuovere il rumore casuale e rivelare la struttura originale e nascosta. Il paper dimostra che questa struttura è un "codice Gabidulin", che è un tipo di enigma matematico che è in realtà piuttosto facile da risolvere una volta conosciuto il modello segreto.

Cosa Viene Effettivamente Violato dal Paper

L'autore non trova solo una piccola crepa; spacca l'intera finestra. Il paper dimostra che questo attacco funziona contro tutti i 16 set di parametri proposti per gli schemi di crittografia EGMC. Ciò significa che ogni versione della serratura che è stata suggerita per l'uso è ora considerata violata.

Per dare un'idea della sua efficacia, il paper esamina un set specifico di numeri che avrebbe dovuto offrire una sicurezza a 128 bit (un livello standard di sicurezza). L'autore mostra che il suo attacco riduce questo livello di sicurezza a soli 35 bit. Nel mondo della crittografia, questo è come passare da una cassaforte con una combinazione di un milione di cifre a una serratura che un bambino potrebbe scassinare in pochi secondi.

Il paper fornisce un esempio concreto di questo potere: utilizzando il loro metodo, i ricercatori sono stati in grado di recuperare la chiave segreta per quel livello di sicurezza a 128 bit in meno di 10 minuti. Non si è trattato solo di un'idea teorica; hanno costruito un programma per computer per farlo.

Cosa Esclude il Paper

È importante notare cosa questo paper dice che non funziona. L'autore spiega che i tentativi precedenti di violare questi codici si basavano su metodi "combinatori", che comportano l'indovinare sia il rimescolamento delle righe che quello delle colonne contemporaneamente. Il paper sostiene che questo vecchio metodo è troppo lento ed inefficiente rispetto al loro nuovo approccio "ibrido".

Inoltre, il paper sostiene contro l'idea che semplicemente rendere più grandi i parametri (aggiungendo più rumore) risolverà il problema per tutti i casi. L'autore mostra che per certi tipi di questi codici — specificamente quando uno dei fattori di rumore (ovvero il numero di righe extra o il numero di colonne extra) è zero — l'attacco diventa così veloce da essere eseguito in "tempo polinomiale". Ciò significa che non importa quanto si aumenti la dimensione della serratura in quei casi specifici, l'attacco sarà comunque abbastanza veloce da violarla. L'unico modo per potenzialmente risolvere il problema, suggerisce il paper, sarebbe cambiare il design fondamentale in modo che entrambi i fattori di rumore siano non nulli e abbastanza grandi da fermare l'attacco, ma l'autore avverte che questo potrebbe rendere le chiavi e i messaggi troppo grandi per essere utili.

Quanto Sono Sicuri?

Il paper è molto fiducioso nei suoi risultati. L'autore non ha solo tirato a indovinare; ha fornito una piena prova matematica di come funziona il suo attacco e l'ha supportata con un'implementazione informatica funzionante. Afferma esplicitamente che il suo attacco rompe tutte le versioni proposte dello schema. Inoltre, confronta i suoi risultati con gli attacchi precedenti, mostrando che il suo metodo è significativamente più veloce e potente. Il paper conclude che gli schemi di crittografia EGMC non sono più sicuri per l'uso e che la comunità della sicurezza deve passare a design differenti.

Sintesi Tecnica: Rottura degli schemi di cifratura EGMC (Enhanced Gabidulin Matrix Codes) tramite MinRank e Gabidulin

Enunciato del Problema
Il documento affronta la sicurezza dei codici a matrice Enhanced Gabidulin (EGMC), un sistema di mascheramento introdotto da Aragon et al. ad Asiacrypt 2024. EGMC è stato progettato per celare la struttura algebrica dei codici a matrice Gabidulin, consentendo schemi di cifratura compatti di tipo McEliece e Niederreiter con ciphertext ridotti (ad esempio, 65 byte per una sicurezza di 128 bit). La sicurezza di EGMC si basa sul problema di Indistinguibilità Decisionale EGMC: l'assunto che un codice EGMC mascherato sia computazionalmente indistinguibile da un codice a matrice casuale. La precedente analisi criptanalitica, specificamente un attacco basato sul kernel MinRank da parte di Porwal et al. (Eurocrypt 2026), ha dimostrato attacchi a tempo esponenziale che hanno violato un sottoinsieme dei set di parametri proposti, lasciandone altri sicuri. L'autore indaga se la costruzione EGMC conservi una struttura nascosta sufficiente per essere violata in modo più efficiente.

Metodologia
L'autore propone un nuovo distinguere "ibrido" e un conseguente attacco di recupero della chiave che combina l'indovinare combinatorio con la risoluzione algebrica. A differenza dei precedenti distinguitori che effettuano il brute-force di entrambe le matrici di compressione riga e colonna, questo attacco indovina solo una matrice di compressione e risolve l'altra utilizzando tecniche algebriche.

L'attacco opera in due direzioni primarie:

Guess- $V$ -solve- $U$ : l'attaccante indovina una matrice di compressione delle colonne $V$ e risolve algebricamente una matrice di compressione delle righe $U$ .
Guess- $U$ -solve- $V$ : l'attaccante indovina una matrice di compressione delle righe $U$ e risolve per una matrice di compressione delle colonne $V$ .

Modellazione Algebrica e Risoluzione
Una volta indovinata una matrice di compressione valida, il codice pubblico viene compresso in un sottospazio equivalente a un codice Gabidulin corto (specificamente un codice $[k+1, k]$ ). L'autore modella la condizione per cui questo codice compresso debba essere un iperpiano $F_{q^m}$ annullato da un vettore specifico. Ciò porta a un sistema di equazioni bilineari che, mediante linearizzazione, produce un sistema lineare omogeneo sul campo di estensione $F_{q^m}$ .

Il nucleo dell'attacco consiste nel trovare una soluzione di rango 1 all'interno del kernel di questo sistema lineare. L'autore osserva che il kernel ammette una base con voci nel campo base $F_q$ . Di conseguenza, il problema si riduce al trovare una combinazione lineare di queste matrici di base che risulti in una matrice di rango 1. Questo viene formulato come un sistema di equazioni quadratiche (annullamento dei minori $2 \times 2$ ).

Per risolvere questo sistema quadratico in modo efficiente, l'autore impiega il metodo degli autovalori (metodo dell'autovalore di Stickelberger) per sistemi polinomiali a dimensione zero. Sfrutta la stabilità di Frobenius del kernel per eseguire i calcoli sul campo più piccolo $F_q$ piuttosto che su $F_{q^m}$ , riducendo significativamente la complessità. Una congettura chiave (Congettura 1) postula che l'algebra quoziente dell'ideale generato dai minori abbia una dimensione pari a $m$ , garantendo che il sistema sia a dimensione zero e risolvibile tramite autovalori.

Contributi Chiave

Distinguere Ibrido: Il documento introduce un distinguere che evita il costo del brute-force completo dei metodi precedenti risolvendo algebricamente una matrice di compressione.
Recupero della Chiave in Tempo Polinomiale: L'autore dimostra che se uno dei fattori di appendice $\ell_1$ o $\ell_2$ è zero, l'attacco diventa a tempo polinomiale. Ciò accade perché il fattore di indovinare esponenziale svanisce, lasciando solo il passaggio di risoluzione algebrica, che recupera la matrice di compressione nascosta in modo efficiente.
Estensione del Codice: Una volta recuperato un codice Gabidulin equivalente punzonato (corto), l'autore fornisce un algoritmo in tempo polinomiale per estendere questo codice fino a un codice Gabidulin segreto equivalente a lunghezza intera, sfruttando la struttura $q$ -Frobenius dei codici Gabidulin.
Decrittazione Universale: La chiave segreta equivalente recuperata (trapdoor) permette la decrittazione di entrambi i ciphertext EGMC-McEliece e EGMC-Niederreiter.

Risultati
L'attacco rompe tutti i 16 set di parametri proposti per gli schemi di cifratura EGMC-Niederreiter.

Riduzione della Sicurezza: Per il set di parametri che punta a 168 bit di sicurezza con parametri $(2, 17, 37, 4, 0)$ , l'attacco riduce il livello di sicurezza dichiarato da 186 bit a circa 35 bit.
Efficienza: Nell'implementazione dell'autore, la chiave segreta equivalente per il set di parametri a 128 bit viene recuperata in meno di 10 minuti.
Confronto: L'attacco supera i precedenti migliori attacchi (combinatori e basati su MinRank) con ampi margini, come mostrato nella Tabella 1 del documento.

Significatività e Rivendicazioni
Il documento sostiene che la costruzione EGMC, così come proposta, non fornisce sicurezza post-quantistica per le specifiche famiglie di parametri dove $\ell_1 = 0$ o $\ell_2 = 0$ . L'autore argomenta che aumentare semplicemente i parametri senza cambiare la costruzione di mascheramento non ripristina la sicurezza per queste famiglie, poiché il passaggio di risoluzione algebrica rimane a tempo polinomiale.

L'autore nota che una potenziale riparazione richiederebbe di mantenere sia $\ell_1$ che $\ell_2$ non nulli e sufficientemente grandi da garantire che il minimo delle due direzioni di attacco superi il livello di sicurezza desiderato. Tuttavia, avverte che aumentare direttamente questi parametri aumenta direttamente le dimensioni della chiave pubblica e del ciphertext, e resta da indagare se tale riparazione rimarrebbe competitiva con altri schemi basati sui codici. Il documento conclude che gli attuali parametri EGMC sono insicuri e che l'attacco proposto fornisce sia un distinguere che un meccanismo completo di recupero della chiave.

La Grande Scoperta del Paper

Cosa Viene Effettivamente Violato dal Paper

Cosa Esclude il Paper

Quanto Sono Sicuri?

Articoli simili