Public Key Encryption from High-Corruption Constraint Satisfaction Problems

1. Il Problema e il Contesto

L'articolo affronta la sfida fondamentale di costruire schemi di Crittografia a Chiave Pubblica (PKE) basati su ipotesi di difficoltà computazionale diverse e potenzialmente più robuste rispetto ai problemi classici (fattorizzazione, logaritmo discreto, reticoli), che potrebbero essere vulnerabili ai computer quantistici o a futuri breakthrough matematici.

Il lavoro si concentra sui Problemi di Soddisfacimento di Vincoli (CSP) con un tasso di corruzione estremamente alto ($1 - o(1)$). In un CSP standard, si cerca un'assegnazione nascosta ("planted") che soddisfi la maggior parte dei vincoli. In questo contesto, la maggior parte dei vincoli viene sostituita da valori casuali (corruzione), rendendo il problema apparentemente indistinguibile da un insieme di vincoli puramente casuali.

L'obiettivo è dimostrare che è possibile costruire un PKE sicuro basandosi sull'intrattabilità di due specifici CSP ad alta corruzione, superando i limiti di sicurezza "quasi-polinomiale" ($\lambda^{O(\log \lambda)}$) tipici delle soluzioni precedenti in questo dominio, raggiungendo invece una sicurezza quasi-esponenziale.

2. Metodologia e Ipotesi di Lavoro

Gli autori introducono due nuove ipotesi di difficoltà (congetture) basate su CSP ad alta corruzione:

1. LARP-CSP (Large Alphabet Random Predicate CSP):

   • Definito su un grafo dei fattori (factor graph) che è fortemente espansivo (ma non necessariamente casuale).
   • Utilizza un alfabeto grande ($\Sigma$) e predicati casuali ($f_i: \Sigma^k \to \Gamma$).
   • La maggior parte delle uscite dei predicati viene sostituita da valori casuali con probabilità $1 - o(1)$.
   • L'ipotesi è che sia computazionalmente intrattabile distinguere tra un insieme di vincoli casuali e uno in cui esiste un'assegnazione nascosta che soddisfa la maggior parte dei vincoli non corrotti.

2. kXOR ad Alta Corruzione:

   • Definito su un grafo dei fattori casuale.
   • Simile al problema kXOR standard, ma con un tasso di corruzione di $1 - o(1)$ (invece di una corruzione polinomiale inversa).
   • L'ipotesi è che distinguere tra un vettore casuale e uno derivato da una somma XOR nascosta (con alta corruzione) sia intrattabile.

Tecnica Chiave: Piantare Trappole (Trapdoors)
Il cuore della metodologia è un nuovo metodo per "piantare" una trappola crittografica. Gli autori utilizzano il grafo dei fattori esteso per etichette (label extended factor graph) di un CSP per nascondere la struttura di un codice di correzione d'errore all'interno di un altro CSP.

• Durante la generazione della chiave pubblica, viene creato un grafo apparentemente casuale (basato su LARP-CSP) che contiene, come sottorete nascosta, la struttura di un codice lineare espansivo.
• La chiave privata consiste nella mappa che identifica dove si trova questa sottorete nascosta all'interno della matrice pubblica.

3. Contributi Chiave

A. Costruzione di un Codice di Correzione d'Errore Unico

Gli autori forniscono la prima costruzione uniforme ed esplicita di un codice di correzione d'errore con le seguenti proprietà:

• Matrice generatrice a bassa densità (LDGM) e fortemente espansiva.
• Capacità di decodificare efficientemente (o distinguere) anche con una frazione di corruzioni pari a $1 - o(1)$.
• Questo risolve un problema aperto, poiché lavori precedenti (es. Oliveira, Santhanam, Tell) avevano dimostrato l'esistenza di tali codici solo in modo non costruttivo.

B. Schemi di Sicurezza Quasi-Esponenziale

A differenza degli schemi PKE basati su CSP ad alta corruzione precedenti (che offrivano sicurezza quasi-polinomiale a causa di un limite di forza bruta sulla dimensione logaritmica del componente nascosto), questo schema evita la decrittazione per forza bruta.

• Risultato: Sicurezza plausibilmente quasi-esponenziale della forma $\exp(2^{\log^{\Omega(1)} \lambda})$, che è significativamente superiore alla sicurezza quasi-polinomiale e si avvicina alla sicurezza sub-esponenziale.

C. Prove di Intrattabilità (Lower Bounds)

Per supportare le loro congetture, gli autori dimostrano una serie di limiti inferiori che escludono molte classi di attacchi noti:

• Attacchi di Embedding a Bassa Complessità: Dimostrano che l'entropia massiccia dei predicati casuali rende il problema immune agli attacchi che sfruttano grafi dei fattori strutturati (come quelli che rompono il PRG di Goldreich su espansori specifici).
• Algoritmi a Polinomi di Basso Grado: Dimostrano che algoritmi basati su polinomi di grado fino a $n^{0.99}$ non possono distinguere le distribuzioni.
• Rifutazioni del Calcolo Polinomiale: Dimostrano che non esistono rifutazioni efficienti (di dimensioni inferiori a $\exp(n^{0.99})$) per il sistema di equazioni polinomiali associato al problema.

4. Risultati Principali

• Teorema 1.3: Se le congetture LARP-CSP e kXOR ad alta corruzione sono vere, allora esiste uno schema di PKE semanticamente sicuro.
• Costruzione Esplicita: Viene fornito un algoritmo probabilistico esplicito per generare la matrice generatrice espansiva necessaria per lo schema, basato su codici di Reed-Muller a basso tasso.
• Robustezza: Lo schema rimane sicuro anche se l'avversario conosce la struttura del grafo dei fattori, purché i predicati siano casuali e ad alta entropia.

5. Significato e Impatto

1. Nuova Fonte di Difficoltà: Introduce una nuova classe di problemi (CSP ad alta corruzione su grafi espansivi) come fonte credibile per la crittografia a chiave pubblica, ampliando il panorama delle ipotesi di sicurezza oltre la teoria dei numeri e i reticoli.
2. Superamento del Limite Quasi-Polinomiale: Rappresenta il primo schema PKE basato su CSP ad alta corruzione che non ricorre a un algoritmo di decrittazione di tipo "guess-and-check" esponenziale su una componente logaritmica, permettendo così di raggiungere livelli di sicurezza molto più elevati.
3. Approccio "Win-Win": Sostiene che anche se le congetture venissero smentite (rompendo lo schema), il processo di ricerca fornirebbe una comprensione profonda della difficoltà media dei problemi CSP e della relazione tra struttura e casualità, un valore intrinseco per la teoria della complessità.
4. Avanzamenti nella Teoria dei Codici: La costruzione esplicita di codici espansivi decodificabili con corruzioni massicce è un risultato significativo indipendente dalla crittografia, con potenziali applicazioni nella teoria dell'informazione e nell'elaborazione dei dati.

In sintesi, questo lavoro propone un cambio di paradigma nella costruzione della crittografia a chiave pubblica, spostando l'attenzione verso problemi di soddisfacimento di vincoli altamente rumorosi e dimostrando che, con le giuste strutture matematiche (espansori e codici Reed-Muller), è possibile ottenere sicurezza robusta e livelli di protezione superiori a quelli precedentemente ottenibili in questo contesto.