In crittografia una dimostrazione a conoscenza zero o protocollo a conoscenza zero è un metodo utilizzato da un soggetto per dimostrare ad un altro soggetto che una affermazione (solitamente matematica) è vera, senza rivelare nient'altro oltre alla veridicità della stessa.
Esempio astratto
C'è una storia ben conosciuta per presentare alcune delle idee alla base della dimostrazione a conoscenza zeroJean-Jacques Quisquater, Louis C. Guillou, Thomas A. Berson. How to Explain Zero-Knowledge Protocols to Your Children. Advances in Cryptology - CRYPTO '89: Proceedings, v.435, p.628-631, 1990. pdf. È uso comune chiamare le due parti in una dimostrazione a conoscenza zero Peggy (chi dimostra l'affermazione) e Victor (chi verifica l'affermazione).
In questa storia, Peggy ha scoperto la parola segreta usata per aprire la porta magica in una caverna. La caverna ha la forma di un cerchio, con l'entrata su un lato e la porta magica che blocca l'altro lato. Victor dice che la pagherà per il segreto, ma non prima di essere sicuro che lei lo conosca davvero. Peggy si dice d'accordo a rivelargli il segreto, ma non prima di aver ricevuto i soldi. Pianificano quindi uno schema con il quale Peggy può dare prova a Victor di conoscere la parola senza rivelargliela.
Dapprima, Victor aspetta fuori dalla caverna mentre Peggy entra. Etichettiamo il sentiero sinistro e quello destro, partendo dall'entrata, con A e B. Peggy sceglie a caso uno dei due sentieri. Quindi, Victor entra nella caverna e grida il nome del sentiero che Peggy dovrà utilizzare per ritornare indietro, fra A e B, preso a caso. Se si ipotizza che lei conosca veramente la parola magica, è facile: apre la porta, se necessario, e ritorna attraverso il sentiero desiderato. È da notare che Victor non conosce il sentiero per il quale Peggy è entrata.
Comunque, supponiamo che Peggy non conosca la parola. Allora, sarebbe in grado di tornare attraverso il sentiero chiamato se Victor avesse scelto il nome dello stesso sentiero per cui lei era entrata. Poiché Victor ha scelto A o B a caso, avrebbe il 50% di probabilità di indovinare correttamente. Se i due ripetessero questo espediente molte volte (ad esempio, venti volte una dopo l'altra), la possibilità per Peggy di adempiere in modo corretto, senza conoscere davvero la parola magica, a tutte le richieste di Victor, diventerebbe statisticamente molto piccola (in virtù della probabilità di eventi indipendenti).
Perciò, se Peggy appare in modo "affidabile" all'uscita chiamata da Victor, questo può concludere che molto probabilmente conosca davvero la parola segreta.
Definizione Una dimostrazione a conoscenza zero deve soddisfare tre proprietà: Completezza: se l'affermazione è vera, un dimostratore onesto potrà convincere del fatto un verificatore onesto (cioè chi segue esattamente il protocollo). Correttezza: se l'affermazione è falsa, nessun dimostratore imbroglione potrà convincere il verificatore onesto che essa è vera, o meglio la probabilità di riuscire a convincerlo può essere resa bassa a piacere. Conoscenza zero: se l'affermazione è vera, nessun verificatore imbroglione potrà sapere altro che tale informazione. Questo fatto è formalizzato mostrando che a ogni verificatore imbroglione può essere associato un simulatore che, se gli viene data solo l'affermazione da provare (e nessun accesso al dimostratore), può ricavare una trascrizione che "sembra" un'interazione tra il dimostratore onesto e il verificatore imbroglione.
Le prime due sono le proprietà della classe più generale dei sistemi interattivi di dimostrazione; la terza è specifica per le dimostrazioni a conoscenza zero. In particolare la prima caratteristica risponde alla completezza come intesa comunemente in logica ("il vero è derivabile", informalmente), mentre la seconda non è direttamente legabile alla correttezza (per la quale "il derivabile è vero": difatti la correttezza di una dimostrazione interattiva è definita proprio come sopra ed è diversa dalla nozione solita di soundness); la componente saliente è ovviamente la terza.
La ricerca nell'ambito di prove a conoscenza zero è stata promossa dai sistemi di autenticazione in cui una parte vuole provare la propria identità ad una seconda parte attraverso una qualche informazione segreta (come ad esempio una password) ma vuole che la seconda parte non conosca nulla di questo segreto. Questa è chiamata "prova di conoscenza a conoscenza zero".
Le dimostrazioni a conoscenza zero non sono dimostrazioni in senso matematico poiché c'è sempre una piccola probabilità che un dimostratore imbroglione riesca a convincere un verificatore di una affermazione falsa. In altre parole, questi tipi di algoritmi sono probabilistici e non deterministici. Tuttavia, ci sono tecniche per ridurre questa probabilità a valori piccoli a piacere.
Una definizione formale di dimostrazione a conoscenza zero deve usare un qualche modello di computazione, il principale è la macchina di Turing. Siano P, V e S delle macchine di Turing. Un sistema di dimostrazione interattiva con (P,V) con un linguaggio L è a conoscenza zero se per ogni verificatore probabilistico a tempo polinomiale (PPT) esiste un simulatore PPT di S tale che
Il dimostratore P è modelizzato come se avesse una potenza computazionale illimitata (in pratica P è usualmente una macchina di Turing probabilistica). Intuitivamente, la definizione afferma che un sistema di dimostrazione interattivo (P,V) è a conoscenza zero se per ogni verificatore esiste un efficiente simulatore S che possa riprodurre la conversazione tra P e per ogni input dato. La stringa ausiliaria z nella definizione gioca il ruolo di "conoscenza a priori". La definizione implica che non possa usare nessuna stringa conosciuta a priori per scoprire delle informazioni sulla conversazione con P perché si chiede che se anche a S è data questa conoscenza a priori allora può riprodurre la conversazione tra e P come prima.
La definizione data è quella di conoscenza zero perfetta. La conoscenza zero computazionale è ottenuta richiedendo che le viste del verificatore e del simulatore (ossia di Victor e Peggy rispettivamente) siano solo computazionalmente indistinguibili, data la stringa ausiliaria.
Ad ogni modo, una password è tipicamente troppo corta od insufficientemente casuale per essere usata, in molti schemi di dimostrazione a conoscenza zero. Una dimostrazione a conoscenza zero di password è un tipo speciale di prova a dimostrazione a conoscenza zero specifica per password di lunghezza limitata.
Uno degli usi più affascinanti delle dimostrazioni a conoscenza zero nei protocolli crittografici è rafforzare il comportamento onesto ed allo stesso tempo mantenere la privacy. Grossomodo, l'idea è di forzare l'utente a provare, usando una dimostrazione a conoscenza zero, la correttezza del suo comportamento rispetto al protocollo. Per via della correttezza, sappiamo che l'utente deve comportarsi in modo veramente onesto per essere abile nel fornire una dimostrazione valida. E per via della conoscenza zero, sappiamo che l'utente non compromette la privacy dei suoi segreti nel processo in cui fornisce la dimostrazione. Quest'applicazione delle dimostrazioni conoscenza zero fu usata per la prima volta nella sconvolgente pubblicazione Shafi Goldwasser, Silvio Micali, e Charles Rackoff, sulla computazione sicura multiparte.
Esempio concreto Possiamo estendere questi concetti a un'applicazione crittografica più realistica. In questo scenario, Peggy conosce un ciclo hamiltoniano per un ampio grafo . Victor conosce ma non il ciclo (per esempio, Peggy ha generato e glielo ha rivelato.) Peggy proverà di conoscere il ciclo senza rivelarlo. Un ciclo hamiltoniano in un grafo è solo un modo di implementare la dimostrazione a conoscenza zero; infatti ogni problema NP-completo può essere usato a tal fine, come pure qualche altro tipo di problema difficile, come la fattorizzazione. Ad ogni modo, Peggy non vuole semplicemente rivelare l'hamiltoniano o qualsiasi altra informazione a Victor; vuole mantenere segreto il ciclo (magari Victor è interessato a comprarlo ma vuole una verifica prima, o forse Peggy è l'unica che conosce quest'informazione e sta provando la sua identità a Victor).
Per mostrare di conoscere il ciclo, Peggy gioca assieme a Victor nel seguente modo:
All'inizio di ogni mano, Peggy crea , un grafo isomorfo a , e lo sottopone a Victor. Poiché è banale tradurre un ciclo hamiltoniano tra grafi dato un isomorfismo (ossia è possibile trovare, a partire dal ciclo hamiltoniano di e da un suo isomorfismo per , il ciclo hamiltoniano corrispondente in , e vale anche il caso duale), se Peggy conosce un ciclo hamiltoniano per ne conosce anche uno per . Victor sceglie poi a caso una delle due seguenti domande da porre a Peggy. Può chiederle di mostrare l'isomorfismo tra e oppure può richiederle di mostrare un hamiltoniano in . Nel primo caso, Peggy fornisce le traduzioni di vertice che mappano in (in pratica, applica l'isomorfismo). Victor può certamente verificare che i due siano isomorfi. Nel secondo caso, Peggy traduce il suo ciclo hamiltoniano di nel corrispondente in e lo rivela a Victor. Egli poi ne verifica la validità.
Ad ogni mano, Peggy non sa quale richiesta le verrà fatta finché non avrà dato a Victor il grafo . Perciò, per essere in grado di rispondere correttamente ad ognuna delle due possibili richieste, dev'essere isomorfo a e Peggy deve avere un ciclo hamiltoniano in . Poiché solo un dimostratore a conoscenza di un ciclo hamiltoniano in può essere sempre in grado di rispondere ad entrambe le richieste, Victor (dopo un sufficiente numero di mani, per la natura probabilistica del procedimento), si convince del fatto che Peggy conosce l'informazione, ovvero un ciclo hamiltoniano in .
Però, la risposta di Peggy come vediamo non rivela tale informazione. Ad ogni mano, Victor verrà a conoscenza solo dell'isomorfismo da in o di un hamiltoniano in . Gli servirebbero entrambe le informazioni per un determinato per scoprire il ciclo in , ma ricordiamo che può fare una sola delle due domande ad ogni mano, e che Peggy utilizza ogni volta un nuovo : l'informazione rimane sconosciuta proprio in virtù di quest'ultima condizione, una volta stabilita la prima come regola del gioco immutabile.
Per via della natura degli isomorfismi tra grafi e dei cicli hamiltoniani, Victor non ha guadagno d'informazione circa il ciclo hamiltoniano in dall'informazione che riceve in ogni mano da Peggy.
Se Peggy non conosce l'informazione, può al più generare o un grafo isomorfo a ma non un suo ciclo hamiltoniano, oppure un ciclo hamiltoniano per il grafo che ha sottoposto a Victor, che però non sarebbe isomorfo a . In entrambi i casi Victor ha la possibilità di rivolgere a Peggy una domanda che la smaschera: nel primo caso chiedendole di mostrare il ciclo hamiltoniano del grafo proposto, nel secondo caso chiedendole di mostrare l'isomorfismo tra e il grafo proposto. Le probabilità che ha Peggy di riuscire ad ingannare Victor, ovvero di evitare ad ogni mano la domanda che la smaschererebbe, sono pari a , dove è il numero di mani. Per tutti gli usi pratici, è infattibile battere una dimostrazione conoscenza zero con un numero di mani ragionevole a garanzia.
Varianti del modello Differenti varianti della dimostrazione a conoscenza zero possono essere definite formalizzando il concetto intuitivo di cosa s'intenda per l'output del simulatore "sembra" l'esecuzione del protocollo effettivo di cui si parlava sopra: Parliamo di conoscenza zero perfetta se le due distribuzioni associate al simulatore ed al protocollo di dimostrazione sono esattamente le stesse; è il caso del primo esempio. Parliamo di conoscenza zero statistica se le distribuzioni non sono necessariamente uguali, ma sono statisticamente vicine, intendendo che la loro differenza statistica è trascurabile (informalmente, possiamo pensare ad una metrica tra le distribuzioni in esame per valutare tale differenza).