Riepilogo Tecnico: Criptanalisi dei Codici di Correzione degli Errori Pseudocasuali basati su LDPC

Definizione del Problema

I Codici di Correzione degli Errori Pseudocasuali (PRC), introdotti a CRYPTO 2024, rappresentano una nuova primitiva crittografica progettata per consentire l'impronta digitale (watermarking) non rilevabile per i Large Generative Models (LLM) e i Generative Image Models (GIM). L'istanza primaria dei PRC, nota come LDPC-PRC, si basa su codici Low-Density Parity-Check e dichiara la propria sicurezza sulla difficoltà dei problemi Learning Parity with Noise (LPN) e planted XOR.

Nonostante le forti garanzie asintotiche teoriche, la sicurezza concreta di LDPC-PRC sotto configurazioni di parametri pratici rimane inesplorata. La letteratura esistente suggerisce che i PRC possano essere vulnerabili ad attacchi di distinzione in tempo quasi-polinomiale, ma non è stata condotta alcuna analisi rigorosa per quantificare tali vulnerabilità in scenari di implementazione reali. Questa lacuna lascia le proprietà di undetectability (non rilevabilità) e robustezza degli schemi di watermarking basati su PRC non verificate contro avversari pratici.

Metodologia

Questo lavoro presenta la prima criptanalisi concreta di LDPC-PRC, concentrandosi su due specifici schemi di watermarking: $\Pi_{LLM}$ (per la generazione di testo) e $\Pi_{GIM}$ (per la generazione di immagini). Gli autori propongono tre nuovi attacchi mirati alla undetectability e alla robustezza dello schema, analizzando la loro complessità sotto configurazioni di parametri realistiche derivate da modelli allo stato dell'arte (DeepSeek e Stable Diffusion).

1. Nuovi Attacchi Crittografici

Gli autori progettano tre attacchi con obiettivi differenti:

• Attacco-I (Recupero Parziale della Chiave Segreta): Questo attacco mira alla proprietà di undetectability. Adattando gli algoritmi di Information Set Decoding (ISD) utilizzando un approccio Meet-in-the-Middle (MITM), l'avversario recupera un sottoinsieme dei vettori di riga della chiave segreta dalla chiave pubblica. I vettori recuperati permettono all'avversario di distinguere tra codewhar la vettori casuali con una probabilità schiacciante, rompendo efficacementmente la undetectability.
• Attacco-II (Distinguere Chiavi Deboli): Questo attacco sfrutta una vulnerabilità nella procedura di generazione delle chiavi ($KeyGen$). Gli autori osservano che nelle attuali implementazioni, la matrice della chiave pubblica $G$ può contenere righe identiche con una probabilità non trascurabile (una "chiave debole"). Un avversario può rilevare queste non uniformità statistiche per distinguere il contenuto con watermark dal rumore casuale in tempo lineare, bypassando la necessità di un complesso recupero della chiave.
• Attacco-III (Attacco di Overlay del Rumore): Questo attacco mira alla proprietà di robustezza. Recuperando il vettore di rumore Bernoulli originale $e$ tramite lo Syndrome Decoding, un avversario costruisce un vettore di overlay malevolo $e'$. Tale vettore è progettato in modo che, quando aggiunto al codeword, il peso totale del rumore superi la soglia di correzione del decoder, causando un fallimento della decodifica (rimozione del watermark). Crucialmente, questo attacco sfrutta il divario tra i limiti teorici del rumore e i tassi di rumore concreti inferiori osservati nelle implementazioni pratiche.

2. Analisi della Complessità Concreta

Gli autori analizzano la complessità temporale e di dati di questi attacchi utilizzando set di parametri specifici per $\Pi_{LLM}$ e $\Pi_{GIM}$. Derivano i limiti teorici (Teoremi 1–3) e li validano rispetto a parametri concreti, calcolando i livelli di bit-security (ad esempio, $2^{46}$, $2^{60}$) anziché affidarsi esclusivamente alla notazione asintotica.

3. Valutazione nel Mondo Reale

Per validare le minacce pratiche, gli autori hanno implementato $\Pi_{LLM}$ e $\Pi_{GIM}$ su DeepSeek (LLM) e Stable Diffusion (GIM). Hanno valutato i tassi di successo degli attacchi e l'impatto sulla qualità del contenuto. In particolare, hanno scoperto che per $\Pi_{LLM}$, ottenere watermark rilevabili richiede un'alta entropia dei token, il che degrada severamente la leggibilità del testo, rendendo lo schema impraticabile per la generazione di testi di alta qualità.

Contributi Chiave e Risultati

1. Violazione della Undetectability

• Attacco-I: Ha dimostrato che il recupero parziale della chiave segreta è fattibile. Per $\Pi_{GIM}$, il livello di sicurezza rimane al di sotto di 46 bit in tutte le scelte di parametri. Per $\Pi_{LLM}$, l'attacco ha successo con una probabilità schiacciante.
• Attacco-II: Ha rivelato che le chiavi deboli si verificano con una probabilità vicina al 100% per specifici parametri (ad esempio, $t=3, 4$) in entrambi gli schemi LLM e GIM. Ciò consente attacchi di distinzione in tempo polinomiale, minando completamente la undetectability in questi regimi.

2. Violazione della Robustezza

• Attacco-III: Ha dimostrato che il livello di sicurezza di $\Pi_{LLM}$ non può superare i 75 bit per $n \le 2^{17}$ sotto attacchi di overlay del rumore. Per $\Pi_{GIM}$, il livello di sicurezza concreta è inferiore a 60 bit a causa del basso tasso di rumore concreto ($\eta \ll \rho$).
• Validazione Sperimentale: Su Stable Diffusion, gli autori hanno ottenuto tassi di successo della rimozione del watermark dal 67% al 96% a seconda del limite di perturbazione ($\delta$), dimostrando che la robustezza è facilmente compromessa.

3. Limitazioni Pratiche di $\Pi_{LLM}$

La valutazione su DeepSeek ha rivelato un compromesso fondamentale: per soddisfare i limiti di correzione degli errori di LDPC-PRC, l'LLM deve generare token ad alta entropia (bassa confidenza). Ciò risulta in un testo che è o non rilevabile (bassa entropia) o illeggibile (alta entropia). Di conseguenza, gli autori concludono che $\Pi_{LLM}$ è impraticabile per il watermarking di testi di alta qualità nel mondo reale.

4. Difese Proposte

Il documento propone tre strategie di mitigazione:

• Raccomandazioni sui Parametri: Aumentare la lunghezza del codice $n$ e il peso della riga $t$ può elevare la complessità dell'attacco. Tuttavia, raggiungere una sicurezza di 128 bit richiede $n > 2^{24}$, il che supera la lunghezza massima di output degli attuali modelli allo stato dell'arte ($2^{15}$).
• Revisione della Generazione delle Chiavi: È proposta una versione modificata dell'algoritmo $KeyGen$ (Algoritmo 2) che utilizza l'eliminazione gaussiana per eliminare la probabilità di generare chiavi deboli, mitigando l'Attacco-II.
• Regolazioni dell'Implementazione: Per i GIM, si suggerisce di aumentare il peso del vettore di rumore aggiunto per colmare il divario tra i tassi di rumore teorici e concreti, aumentando così la complessità dell'Attacco-III.

Significato e Rivendicazioni

Il documento sostiene di fornire la prima valutazione sistematica della sicurezza dei PRC, colmando il divario tra la teoria asintotica e l'implementazione pratica. Gli autori affermano che:

1. Le Garanzie di Sicurezza sono Compromesse: La sicurezza dichiarata di LDPC-PRC è insufficiente in tutti i regimi praticamente sostenibili. Gli attacchi possono rilevare i watermark con una probabilità schiacciante a costi significativamente inferiori a 128 bit.
2. Impossibilità Pratica per gli LLM: A causa dei vincoli intrinseci dei grandi modelli generativi (specificamente la lunghezza dell'output e l'entropia dei token), ottenere una sicurezza di 128 bit per il watermarking degli LLM tramite LDPC-PRC è attualmente impraticabile.
3. Necessità di una Valutazione Rigorosa: Il lavoro evidenzia che le assunzioni di durezza teorica (LPN/planted XOR) non si traducono automaticamente in sicurezza concreta quando vengono considerati dettagli specifici di implementazione (come le euristiche di generazione delle chiavi e i tassi di rumore).

Gli autori concludono che, sebbene il watermarking delle immagini basato su PRC possa ancora ammettere implementazioni pratiche con una qualità accettabile, l'attuale stato dei PRC per gli LLM richiede una significativa rivalutazione dei parametri e delle strategie di implementazione prima di un dispiegamento diffuso.