Una prova crittografica può nascondere il suo segreto rendendo difficile provare l'assenza del simulatore

Il trucco non è provare che il segreto è nascosto

Partiamo dalla versione più semplice della conoscenza zero.

Alice vuole convincere Bob che un Sudoku ha una soluzione. Se gli manda la soluzione, Bob è convinto, ma il puzzle è rovinato. Quello che vuole è più strano: una prova che una soluzione esiste, senza rivelare la soluzione.

Questa è la promessa di una prova zero-knowledge. Il prover, Alice, convince il verifier, Bob, che un enunciato è vero rivelando nulla oltre alla verità dell’enunciato.

Il problema è che questa promessa costa qualcosa. Una prova matematica ordinaria ha due caratteristiche comode. È un messaggio: la scrivi, la consegni e te ne vai. Ed è perfettamente solida: un enunciato falso non ha alcuna prova valida. I risultati classici di impossibilità dicono che lo zero-knowledge deve rinunciare a entrambe le cose, e non solo alla coppia: ciascuna è vietata anche da sola.

Primo, una prova zero-knowledge ha bisogno di conversazione. Se Alice manda un solo messaggio, senza setup fidato preparato in anticipo, la garanzia zero-knowledge collassa, qualunque solidità tu sia disposto a sacrificare in cambio.

Secondo, una prova zero-knowledge ha bisogno di una piccola tolleranza all’errore. Chiedere solidità perfetta finisce per distruggere in silenzio anche l’interazione: un verificatore che non può mai essere ingannato, qualunque scelta casuale faccia, potrebbe fissare quelle scelte in anticipo; e quando il verificatore è prevedibile, Alice può rispondere a tutto con un solo messaggio, cioè il caso che si era già rotto.

Il paper di Rahul Ilango riguarda un modo per aggirare quel doppio muro. Non fingendo che il muro non esista, e non producendo zero-knowledge classico nel setting impossibile. La mossa è più sottile: indebolire ciò che significa “non rivela nulla”, ma indebolirlo in un modo che preserva le proprietà di sicurezza che i crittografi possono davvero testare.

Il risultato si chiama effectively zero-knowledge.

Il vecchio test: esiste un simulatore

Il modo classico di formalizzare lo zero-knowledge usa un aiutante fittizio chiamato simulatore.

L’idea è questa: immagina Jane, che non conosce il segreto di Alice. Se Jane può generare, da sola, prove che sembrano proprio le prove che Bob avrebbe ricevuto da Alice, allora le prove di Alice non hanno insegnato a Bob niente di nuovo. Jane poteva già fingere quell’esperienza senza il segreto di Alice.

Lo zero-knowledge classico chiede quindi un simulatore reale. Deve esistere un algoritmo efficiente che produca prove dall’aspetto finto senza conoscere il segreto, il witness nel gergo; per il Sudoku, il witness è semplicemente la griglia risolta.

Questa definizione è potente, ma è anche esattamente dove mordono le vecchie impossibilità. L’intuizione è questa. Una prova davvero non interattiva è solo una stringa. Una volta che Bob ha quella stringa, può mostrarla ad altri: ha acquisito la capacità di provare l’enunciato ad altri, cosa che suona già come più di “nulla”. I teoremi classici rendono quell’intuizione precisa nelle impossibilità sopra.

Una versione mega-Sudoku della differenza

Ecco un modo volutamente semplificato per sentire la differenza.

Non usare un Sudoku ordinario 9 per 9 per la parte seria dell’analogia. È troppo piccolo e troppo finito: un computer può semplicemente risolverlo o provare che non ha soluzione. Immagina invece una famiglia di puzzle MegaSudoku(n). Scala la regola solita: scegli una dimensione di blocco n, lascia N = n^2, e costruisci una griglia N per N divisa in blocchi n per n, con N simboli. Il Sudoku ordinario è solo il caso minuscolo n = 3, N = 9: una griglia 9 per 9, blocchi 3 per 3 e nove simboli. La storia di complessità delle prove inizia solo quando n può crescere, e quando la griglia può portare gadget extra che la fanno comportare come una formula SAT vestita da Sudoku. Una formula SAT è solo una lista di vincoli sì/no: puoi assegnare valori vero/falso alle variabili in modo che ogni vincolo sia soddisfatto?

Il witness resta facile da immaginare. Alice conosce un riempimento completo valido del mega-Sudoku. Bob vuole essere convinto che un tale riempimento esista, ma Alice non vuole rivelarlo. Se manda l’intero riempimento, Bob è convinto, ma il segreto è perso.

Nella versione classica zero-knowledge, Alice e Bob interagiscono. Un vecchio modello mentale usa tessere coperte. Alice nasconde la griglia risolta, rinomina segretamente i simboli prima di ogni round e lascia Bob ispezionare un vincolo locale scelto a caso: una riga, una colonna, un box o un gadget. Se le celle aperte mostrano simboli tutti diversi, Bob guadagna fiducia. Poi tutto viene ricoperto e i simboli sono rinominati da capo.

Questo non è il protocollo del paper. È il modello mentale dello zero-knowledge classico:

• Alice e Bob vanno avanti e indietro.
• Bob sceglie controlli casuali.
• Alice rivela solo consistenza locale, non l’intera soluzione.
• La prova di privacy funziona mostrando che la vista di Bob avrebbe potuto essere generata senza la soluzione segreta di Alice.

Lo zero-knowledge classico è quindi costruito attorno a un fatto positivo:

Un simulatore esiste davvero.

Ora rimuovi le parti comode. Alice manda una stringa di prova e se ne va. Non c’è setup fidato, nessuna stringa casuale condivisa preparata in anticipo, e Bob non deve mai accettare un puzzle falso. È il setting in cui lo zero-knowledge classico non sopravvive.

Serve ancora un personaggio. Fissa un rulebook: un sistema formale di prova, nel senso logico, cioè un insieme fisso di assiomi più regole meccaniche per controllare prove matematiche scritte. ZFC, gli assiomi standard della matematica, è l’esempio canonico. Da qui in poi tutto è relativo a un rulebook scelto in anticipo, e la scelta è flessibile: la costruzione funziona per qualunque rulebook fissato, ZFC incluso.

La versione in stile Gödel mantiene la storia del mega-Sudoku ma cambia la prova.

Scegli un secondo sistema di vincoli della stessa dimensione mostrata, chiamalo D. Per la storia, S e D sono due puzzle MegaSudoku(n) nello stesso formato. Dietro le quinte, D può essere nato come una formula logica difficile di dimensione diversa; se serve, può essere riempito con vincoli dummy innocui per adattarsi alla stessa griglia. D è costruito da una formula logica che è in realtà insoddisfacibile: non esiste alcuna assegnazione di valori che renda veri tutti i suoi vincoli, proprio come un puzzle rotto non ha griglia completata valida.

Ma D non deve essere un puzzle rotto facile da esporre. Deve essere falso in un modo che il rulebook scelto non possa certificare con un argomento breve. Se il rulebook potesse confutare D con una prova breve, la storia sotto collasserebbe: la via alternativa che avrebbe potuto produrre prove senza il segreto di Alice sarebbe formalmente esclusa, e con essa la garanzia di privacy. Quindi D è scelto da una famiglia che il rulebook fissato non può confutare efficientemente.

La prova a un messaggio di Alice riguarda allora un enunciato o/o:

o il vero mega-Sudoku S ha una soluzione, oppure il decoy D ha una soluzione.

Questo è il legame logico. D non è generato in qualche modo magico che renda vero S. La prova non dice “D non ha soluzione, quindi S ha soluzione.” Prova la disgiunzione S o D. La solidità perfetta dice che una disgiunzione falsa non può avere una prova valida. Poiché D è falso nella realtà, l’unico modo in cui la disgiunzione può essere vera è che S sia vero. Quindi, se la prova è accettata, S deve avere una soluzione.

Ma per la parte in stile zero-knowledge, chiedi che cosa succederebbe se D avesse una soluzione. Quella soluzione decoy funzionerebbe da witness alternativo. Permetterebbe di produrre prove senza conoscere la vera soluzione mega-Sudoku di Alice: un simulatore. In realtà D non ha soluzione, quindi questa via è chiusa. Il punto è che il rulebook non può provare efficientemente che è chiusa.

D ha quindi due lavori. Per la solidità, D è falso, quindi una prova valida di “S o D” forza S. Per l’effective zero-knowledge, D è difficile da confutare, quindi il rulebook non può escludere rapidamente la via decoy che avrebbe reso possibile la simulazione.

Il test di sicurezza non è più:

Possiamo provare che un simulatore esiste davvero?

Diventa:

Il tuo rulebook può provare efficientemente che il simulatore è impossibile?

Se la risposta è no, segue qualcosa di sorprendentemente forte: ogni garanzia di sicurezza che (a) può essere osservata eseguendo un test e (b) segue dimostrabilmente, dentro quel rulebook, dall’esistenza di un simulatore, vale davvero. Un attacco riuscito a una di esse ammonterebbe alla confutazione breve mancante, e quella confutazione breve non esiste. Questa è la parte “effective” di effectively zero-knowledge.

Il contrasto da aula è:

Zero-knowledge classico: le prove sono sicure perché esiste un simulatore.

Zero-knowledge effettivo in stile Gödel: le prove sono trattate come sicure per test di sicurezza osservabili perché il rulebook non può provare efficientemente che il simulatore è impossibile.

Il secondo claim è più debole. Ed è anche il motivo per cui il paper può mantenere le tre caratteristiche che rompevano la versione classica: un messaggio, niente setup e solidità perfetta.

Il nuovo test: non puoi provare che il simulatore è assente

Il rilassamento di Ilango cambia la domanda.

Lo zero-knowledge classico chiede:

Esiste un simulatore?

L’effectively zero-knowledge chiede qualcosa di più debole:

Il tuo rulebook scelto può provare efficientemente che non esiste alcun simulatore?

Sembra un trucco tecnico, ma è il cuore dell’idea. La costruzione vive in uno stato strano: un simulatore in realtà non esiste, e il paper lo dice esplicitamente, ma il rulebook fissato non può provare efficientemente che non esiste. Se ogni conseguenza cattiva che ti interessa richiederebbe una tale confutazione, il sistema si comporta comunque come zero-knowledge per quelle conseguenze.

Qui entra Gödel. Non come decorazione, e non come “Gödel rende sicura la crittografia”. Il collegamento è proof-theoretic. Un rulebook è detto ottimale se è, in un senso preciso, il migliore possibile: quando qualunque rulebook può confutare una formula del tipo rilevante con una prova breve, anche il rulebook ottimale può farlo, con una prova al massimo polinomialmente più lunga. Krajíček e Pudlák congetturarono nel 1989 che non esiste alcun sistema di prova ottimale. Qualunque rulebook tu fissi, qualche altro rulebook prova qualche famiglia di enunciati veri molto più succintamente.

Il paper assume questa congettura in una forma “infinitely often” leggermente più forte, standard quando le congetture sono usate crittograficamente. Il payoff, tramite un teorema di Krajíček e Pudlák, è concreto: per ogni rulebook esiste una sequenza di formule davvero insoddisfacibili che quel rulebook non può confutare con prove brevi, e che un algoritmo efficiente può generare. Quest’ultima proprietà, l’uniformità, trasforma l’idea da esistenza astratta ad algoritmo reale che Alice può eseguire: i decoy D escono da una catena di montaggio.

La mossa crittografica è mettere al lavoro quella scarsità di potenza dimostrativa.

Che cosa fa la costruzione

Ecco la costruzione del paper, spogliata della forma.

Fissa un rulebook, per esempio ZFC. Sotto l’assunzione di complessità delle prove, esiste una sequenza generabile efficientemente di formule che sono davvero insoddisfacibili, ma per cui il rulebook non ha alcuna prova breve di insoddisfacibilità.

Ora costruisci una prova a un messaggio di questa forma:

o il vero enunciato è soddisfacibile, oppure questa speciale formula difficile è soddisfacibile.

La formula speciale non è soddisfacibile. Quindi, se la macchina di prova sottostante è perfettamente solida, accettare il messaggio significa comunque che il vero enunciato è vero. Questo dà solidità perfetta.

Ma per la sicurezza in stile zero-knowledge, immagina che la formula speciale fosse soddisfacibile. Allora il suo witness potrebbe essere usato per simulare prove senza conoscere il witness reale. La formula non è soddisfacibile nella realtà, ma il rulebook non può provarlo efficientemente. Quindi non può provare efficientemente che il simulatore è impossibile.

Questo è il cardine. Il sistema non nasconde il segreto producendo un simulatore classico. Nasconde il segreto, per una grande classe di test di sicurezza osservabili, dietro l’incapacità del rulebook di certificare che il simulatore è assente.

Che cosa afferma il paper

Il teorema principale arriva a strati. Il risultato centrale è questo:

Sotto un’assunzione crittografica standard, l’esistenza di prove non interattive witness indistinguishable, oggetti ben studiati che seguono da diversi pacchetti di assunzioni stabiliti, e sotto la congettura di complessità delle prove che non esiste alcun sistema di prova ottimale (infinitely often), il paper costruisce, per ogni scelta di rulebook, un prover e un verifier a un messaggio per NP/SAT con solidità perfetta e senza setup che è effectively zero-knowledge relativo a quel rulebook. NP/SAT è il denominatore comune “più difficile” dei problemi tipo puzzle; il mega-Sudoku è un costume che indossa.

Per il claim più ampio sul preservare proprietà di sicurezza falsificabili, il paper aggiunge un’altra assunzione standard, la credenza di derandomizzazione P = BPP: in breve, la casualità non dà agli algoritmi potere essenziale in più.

Tradotto fuori dal linguaggio dei teoremi:

• La prova è un messaggio.
• Non c’è setup fidato.
• Gli enunciati falsi non possono essere provati.
• Il prover non è zero-knowledge classico: non ha simulatore.
• Ma ogni conseguenza di sicurezza falsificabile, basata su giochi, dello zero-knowledge classico può essere ottenuta in questo setting.

“Falsificabile” conta. Significa che un fallimento di sicurezza può essere testato eseguendo un avversario in un gioco. Molte definizioni crittografiche hanno questa forma: l’avversario può distinguere due cifrati, invertire una funzione, recuperare un witness o vincere un esperimento specificato? Il teorema dà un prover per ciascuna proprietà falsificabile, una alla volta. Un singolo prover che goda di ogni proprietà falsificabile insieme è probabilmente impossibile: il vecchio attacco di riutilizzabilità (“Bob può mostrare la prova ad altri”) è esso stesso una proprietà falsificabile, e qui fallisce davvero. La proposta del paper è che un singolo prover possa plausibilmente coprire tutte le proprietà falsificabili naturali, quelle che compaiono davvero nella pratica crittografica, ma quella parte è un teorema condizionale appoggiato a una nozione informale di “naturale” più una congettura esplicita. La garanzia punta ai fallimenti osservabili, non a ogni significato filosofico o simulation-based di segretezza.

Vale la pena nominare un corollario concreto: la costruzione dà le prime prove non interattive witness hiding con prover uniforme, “una prova di un puzzle non ti aiuta a trovarne la soluzione”, senza interazione e senza setup; un oggetto dal suono modesto che aveva resistito per decenni.

Che cosa non dice

Questa è la sezione che tiene onesto il pezzo.

Non dice che i vecchi teoremi di impossibilità fossero sbagliati. La costruzione li evita cambiando la definizione.

Non dà zero-knowledge ordinario, classico, senza interazione, senza setup e con solidità perfetta. Il paper dice esplicitamente che il prover costruito non ha un simulatore.

Non significa che la prova non possa essere riutilizzata. Una prova a un messaggio può ancora essere mostrata a qualcun altro; il paper non preserva proprietà di tipo deniability. Lo zero-knowledge non interattivo con setup fidato ha la stessa limitazione.

Non significa che questo sia un protocollo pratico pronto per il deployment. È teoria della complessità e fondamenti della crittografia. Il risultato dipende da grandi assunzioni di complessità delle prove e crittografia, e la costruzione riguarda ciò che è possibile in linea di principio.

Non rende “Gödel” una primitiva magica di sicurezza. Il collegamento con Gödel passa per sistemi di prova, sistemi di prova ottimali e analoghi finiti dell’incompletezza. L’intuizione utilizzabile non è “l’incompletezza protegge la tua password”. È: se un rulebook non può provare efficientemente che un simulatore è impossibile, allora attacchi che richiederebbero quella prova possono essere bloccati a livello delle definizioni di sicurezza.

Perché è comunque interessante

La crittografia trasforma spesso la durezza in sicurezza. Fattorizzare è difficile, quindi assunzioni in stile RSA diventano utili. Problemi reticolari sono difficili, quindi la crittografia lattice diventa utile. Qui la durezza è più strana: non “difficile calcolare un segreto”, ma “difficile provare che un certo oggetto di prova non può esistere”.

Per questo il paper sembra insolito. Tratta assiomi e rulebook quasi come risorse crittografiche. L’impossibilità usuale dice che c’è una tensione tra solidità e simulazione. La mossa di Ilango mette quella tensione dietro una tenda proof-theoretic: il simulatore è assente, ma il sistema formale non può esporre efficientemente quell’assenza.

Per un lettore, la parte sorprendente non è che questo sostituirà i sistemi zero-knowledge di oggi. Probabilmente non lo farà, almeno non direttamente. La parte sorprendente è che un limite della logica matematica possa essere usato in modo costruttivo: non solo come muro, ma come una forma di copertura.

Quanto è forte l’evidenza?

È un paper di teoremi, quindi “evidenza” significa qualcosa di diverso rispetto a un paper di biologia o astronomia. La domanda non è se un esperimento si è replicato. È se definizioni, assunzioni e catena di prova sostengono il claim.

La prova è formale, e il paper è esplicito sulle assunzioni. Le assunzioni non sono casuali. Le prove non interattive witness indistinguishable sono oggetti standard in crittografia e seguono da diversi pacchetti di assunzioni stabiliti. La congettura di non esistenza di sistemi di prova ottimali è una congettura centrale in complessità delle prove. P = BPP è una credenza standard di derandomizzazione usata solo per il teorema più ampio sulle proprietà falsificabili.

Il paper sostiene anche che le assunzioni sono il prezzo giusto, non un’impalcatura arbitraria: prova un converso secondo cui sono essenzialmente necessarie. Se costruzioni come questa esistono, allora devono esistere prove non interattive witness indistinguishable e, concedendo funzioni one-way standard, non può esistere alcun sistema di prova ottimale. E le assunzioni sono “win-win”: confutarne una sarebbe già una scoperta importante in complessità delle prove, crittografia o teoria della complessità.

Ma poiché il risultato è condizionale, anche la fiducia è condizionale. Se quelle assunzioni falliscono, l’interpretazione del teorema cambia. E anche se tengono, la garanzia non è zero-knowledge classico pieno; è la versione rilassata e proof-theoretic del paper.

La fiducia giusta è quindi alta che il paper stabilisca un risultato condizionale coerente di possibilità; moderata che le sue assunzioni descrivano il mondo crittografico in cui viviamo; bassa per qualunque conseguenza pratica immediata.

Perché conta

Il paper apre una strada che doveva essere chiusa.

La teoria classica dice: lo zero-knowledge pieno non può essere un messaggio senza setup e non può essere perfettamente solido. Il paper di Ilango dice: se chiediamo le conseguenze dello zero-knowledge che possono essere testate in giochi di sicurezza, e se permettiamo alla definizione di sicurezza di dipendere da ciò che un rulebook può o non può confutare efficientemente, allora molto del comportamento utile può essere recuperato, con un messaggio, senza setup e con solidità perfetta.

Non è un piccolo ritocco definitorio. È un modo diverso di pensare le garanzie crittografiche. Invece di chiedere solo che cosa esiste, chiedi che cosa il tuo rulebook può escludere. Invece di trattare l’improvabilità come un fastidio filosofico, usala come struttura.

Il mondo pratico forse non cambierà domani. Ma la mappa concettuale sì. Ora esiste un senso formale in cui “nessuno può provare efficientemente che il segreto sia trapelato” può essere abbastanza forte da recuperare molte delle protezioni game-based che volevamo da “il segreto non è trapelato”.

È per questo che Gödel sta nel titolo.

Riassunto pulito

Le prove zero-knowledge permettono a un prover di convincere un verifier che un enunciato è vero senza rivelare il witness. I risultati classici di impossibilità dicono che lo zero-knowledge non può essere compresso in un messaggio senza setup e non può avere solidità perfetta. Il paper di Rahul Ilango non confuta quelle impossibilità. Definisce una nozione più debole, effectively zero-knowledge: invece di richiedere che un simulatore esista davvero, richiede che un sistema di prova scelto, un rulebook formale come ZFC, non possa provare efficientemente che nessun simulatore esiste. Sotto grandi assunzioni di crittografia (prove non interattive witness indistinguishable) e complessità delle prove (non esiste alcun sistema di prova ottimale), il paper costruisce prover a un messaggio per NP/SAT, senza setup e con solidità perfetta, che ottengono le conseguenze falsificabili e game-based dello zero-knowledge proprietà per proprietà. Un singolo prover che copra tutte queste proprietà “naturali” è un’estensione ulteriore, in parte congetturale; coprire letteralmente ogni proprietà falsificabile è probabilmente impossibile, perché le prove restano riutilizzabili. Il risultato è teorico e condizionale, non una primitiva deployata, ma mostra un modo nuovo di usare l’improvabilità proof-theoretic come risorsa crittografica.