Immagina di avere qualche conoscenza utile, forse una ricetta segreta o la chiave per un codice. Potresti dimostrare a un amico che possedevi quella conoscenza, senza rivelare nulla al riguardo? Gli informatici hanno dimostrato più di 30 anni fa che si poteva, se si utilizzava quella che viene chiamata prova a conoscenza zero.
Per comprendere in modo semplice questa idea, supponiamo che tu voglia mostrare al tuo amico che sai come attraversare un labirinto, senza rivelare alcun dettaglio sul percorso. Potevi semplicemente attraversare il labirinto entro un limite di tempo, mentre al tuo amico era vietato guardare. (Il limite di tempo è necessario perché, dato abbastanza tempo, chiunque può eventualmente trovare la via d'uscita attraverso tentativi ed errori.) Il tuo amico saprebbe che potresti farlo, ma non saprebbe come.
Le prove a conoscenza zero sono utili ai crittografi, che lavorano con informazioni segrete, ma anche ai ricercatori di complessità computazionale, che si occupano di classificare la difficoltà di diversi problemi. "Gran parte della crittografia moderna si basa su presupposti di complessità, sul presupposto che alcuni problemi siano difficili da risolvere, quindi ci sono sempre state alcune connessioni tra i due mondi", ha affermato Claude Crepeau, uno scienziato informatico presso la McGill University. "Ma [queste] prove hanno creato un intero mondo di connessioni."
Le dimostrazioni a conoscenza zero appartengono a una categoria nota come prove interattive, quindi imparare come funzionano le prime è utile comprendere le seconde. Primo descritta in un articolo del 1985 degli scienziati informatici Shafi goldwasser, Silvio Micali e Charles Rackoff, le dimostrazioni interattive funzionano come un interrogatorio: attraverso una serie di messaggi, una parte (il dimostratore) cerca di convincere l'altra (il verificatore) che una determinata affermazione è vera. Una dimostrazione interattiva deve soddisfare due proprietà. Innanzitutto, un'affermazione vera alla fine convincerà sempre un verificatore onesto. In secondo luogo, se l’affermazione data è falsa, nessun dimostratore – nemmeno uno che finge di possedere una certa conoscenza – può convincere il verificatore, se non con una probabilità trascurabile.
Le dimostrazioni interattive sono di natura probabilistica. Il dimostratore potrebbe rispondere correttamente a una o due domande semplicemente per fortuna, quindi è necessario un numero sufficientemente elevato di sfide, che il dimostratore deve risolvere tutte correttamente, affinché il verificatore diventi sicuro che il dimostratore sa effettivamente che l'affermazione è vera.
Questa idea di interazione è nata quando Micali e Goldwasser, allora studenti laureati presso l'Università della California, Berkeley, si sono interrogati sulla logistica del gioco del poker in rete. Come possono tutti i giocatori verificare che quando uno di loro prende una carta dal mazzo virtuale, il risultato è casuale? Le prove interattive potrebbero aprire la strada. Ma allora, come possono i giocatori verificare che l'intero protocollo – l'intero insieme di regole – sia stato seguito correttamente, senza rivelare la mano di ogni giocatore lungo il percorso?
Per raggiungere questo obiettivo, Micali e Goldwasser aggiunsero una terza proprietà alle due necessarie per una dimostrazione interattiva: la dimostrazione non dovrebbe rivelare nulla della conoscenza stessa, solo la veridicità dell'affermazione. "C'è l'idea di seguire un protocollo, alla fine del quale si crede che [i giocatori di poker] non sappiano niente di più di quello che dovrebbero sapere," ha detto Goldwasser.
Consideriamo l'esempio classico. Alice vuole dimostrare a Bob che un certo grafico G - una raccolta unica di vertici (punti) collegati da bordi (linee) - ha un "ciclo hamiltoniano". Ciò significa che il grafico ha un percorso che visita ogni punto esattamente una volta e termina nello stesso punto da cui è iniziato. Alice potrebbe farlo semplicemente mostrando a Bob il percorso che lo fa, ma ovviamente anche lui conoscerebbe il percorso.
Ecco come Alice può convincere Bob di sapere che esiste un percorso del genere, senza mostrarglielo. Per prima cosa disegna un nuovo grafico, H, non sembra G ma è simile in un modo cruciale: ha lo stesso numero di vertici, collegati negli stessi modi. (Se G ha davvero un ciclo hamiltoniano, significa questa somiglianza H lo farà anche lui.) Quindi, dopo aver coperto ogni bordo H con nastro adesivo, si chiude a chiave H in una scatola e dà la scatola a Bob. Ciò gli impedisce di vederlo direttamente ma le impedisce anche di alterarlo. Poi Bob fa una scelta: può chiedere ad Alice di mostrarlo H è davvero simile a G, oppure può chiederle di mostrargli il ciclo hamiltoniano H. Entrambe le richieste dovrebbero essere facili per Alice, presupponendolo H è davvero abbastanza simile a G, e che conosce davvero il percorso.
Naturalmente, anche se Alice non conosce il ciclo hamiltoniano G, può provare a ingannare Bob disegnando grafici che non sono simili a Go inviando grafici di cui non conosce il percorso. Ma dopo aver giocato più round, la possibilità che Alice inganni Bob ogni volta diventa incredibilmente piccola. Se tutto va bene, alla fine Bob si convincerà che Alice conosce un ciclo hamiltoniano nel grafico G, senza che Bob l'avesse mai visto.
Dopo l’articolo iniziale che descriveva per la prima volta tali dimostrazioni, Micali e due matematici – Oded Goldreich e Avi Wigderson – scoprirono una conseguenza inaspettata con effetti di vasta portata. Ha a che fare con un'importante categoria di problemi di difficoltà più o meno uguale, nota come NP. Questi problemi sono difficili da risolvere, ma le loro soluzioni sono facili da verificare. I tre ricercatori trovato che, se la crittografia è veramente sicura è possibile, allora la soluzione di ogni problema in NP può essere dimostrata anche con una dimostrazione a conoscenza zero. Questo studio ha aiutato i ricercatori concepire varianti di prove a conoscenza zero che non richiedono nemmeno la crittografia sicura in primo luogo; queste sono conosciute come prove interattive multi-prover.
E nel 1988 Micali e altri ha mostrato che se un prover e un verificatore condividono una breve stringa di bit casuali, non è necessaria alcuna interazione. Ciò significava teoricamente che le prove a conoscenza zero non dovevano essere interattive, il che implicherebbe che non fosse necessaria una comunicazione costante tra due parti. Ciò li renderebbe molto più utili ai ricercatori, ma è stato solo dopo la fine del 21° secolo che tali prove hanno preso piede.
“Alla fine degli anni 2000, abbiamo iniziato a vedere l’evoluzione di tecniche efficienti per costruire dimostrazioni a conoscenza zero”, ha affermato Matteo D. Verde, un crittografo della John Hopkins University. "Siamo arrivati al punto in cui ci siamo resi conto: 'Aspetta un secondo, potrebbe esserci un modo per usarlo nella pratica.'"
Ora un sperimentatore potrebbe inviare un singolo messaggio a un verificatore senza che entrambi debbano essere online, e i ricercatori potrebbero creare una dimostrazione molto breve che potrebbe essere verificata rapidamente, anche per problemi molto complicati. Ciò ha portato a diversi usi pratici, come la possibilità di verificare rapidamente la blockchain dopo una transazione di criptovaluta nascondendo i dettagli della transazione. E nel 2016, un gruppo di fisici ha mostrato come le prove a conoscenza zero possono aiutare con il disarmo nucleare: senza rivelare alcun segreto sulla progettazione della sua testata nucleare, un paese potrebbe ora dimostrare agli ispettori nucleari se la testata è attiva o inattiva.
Più recentemente, i progressi nell’informatica quantistica hanno costretto Crépeau a sottoporre a stress test la ricerca passata per assicurarsi che i protocolli a conoscenza zero siano ancora praticabili. Nel 2021, ha aiutato dimostrare che le dimostrazioni interattive multi-provatore mantengono la loro segretezza anche quando sono coinvolti i computer quantistici, ma il raggiungimento dello stesso livello di sicurezza rende il protocollo molto più lento. La scoperta è una buona notizia, ha detto, ma nuove preoccupazioni sorgeranno con l’avanzare della tecnologia.
“Ogni tipo di calcolo che potremmo fare in futuro coinvolgerà i computer quantistici”, ha affermato Crépeau. "Quindi, da bravi crittografi paranoici, ogni volta che valutiamo la sicurezza di un sistema, vogliamo assicurarci che il nostro sistema sia sicuro."
Nota dell'editore: Shafi Goldwasser ha ricevuto un finanziamento dalla Simons Foundation, che finanzia anche questo pubblicazione editoriale indipendente. Le decisioni di finanziamento della Simons Foundation non hanno alcuna influenza sulla nostra copertura.
