Dimostrazione a conoscenza zero

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 zero. È 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à:

1. Completezza: se l'affermazione è vera, un dimostratore onesto potrà convincere del fatto un verificatore onesto (cioè chi segue esattamente il protocollo).
2. 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.
3. 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

              $\forall x\in L,z\in \{0,1\}^{*},View_{\hat {V}}[P(x)\leftrightarrow {\hat {V}}(x,z)]=S(x,z)$

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 ${\hat {V}}$ esiste un efficiente simulatore S che possa riprodurre la conversazione tra P e ${\hat {V}}$ per ogni input dato. La stringa ausiliaria z nella definizione gioca il ruolo di "conoscenza a priori". La definizione implica che ${\hat {V}}$ 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 ${\hat {V}}$ e P come prima.

La definizione data è quella di conoscenza zero perfetta. La conoscenza zero computazionale è ottenuta richiedendo che le viste del verificatore ${\hat {V}}$ 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 $G$. Victor conosce $G$ ma non il ciclo (per esempio, Peggy ha generato $G$ 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 $H$, un grafo isomorfo a $G$, 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 $H$ e da un suo isomorfismo per $G$, il ciclo hamiltoniano corrispondente in $G$, e vale anche il caso duale), se Peggy conosce un ciclo hamiltoniano per $G$ ne conosce anche uno per $H$.
• Victor sceglie poi a caso una delle due seguenti domande da porre a Peggy. Può chiederle di mostrare l'isomorfismo tra $H$ e $G$ oppure può richiederle di mostrare un hamiltoniano in $H$.
• Nel primo caso, Peggy fornisce le traduzioni di vertice che mappano $G$ in $H$ (in pratica, applica l'isomorfismo). Victor può certamente verificare che i due siano isomorfi.
• Nel secondo caso, Peggy traduce il suo ciclo hamiltoniano di $G$ nel corrispondente in $H$ 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 $H$. Perciò, per essere in grado di rispondere correttamente ad ognuna delle due possibili richieste, $H$ dev'essere isomorfo a $G$ e Peggy deve avere un ciclo hamiltoniano in $H$. Poiché solo un dimostratore a conoscenza di un ciclo hamiltoniano in $G$ 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 $G$.

Però, la risposta di Peggy come vediamo non rivela tale informazione. Ad ogni mano, Victor verrà a conoscenza solo dell'isomorfismo da $H$ in $G$ o di un hamiltoniano in $H$. Gli servirebbero entrambe le informazioni per un determinato $H$ per scoprire il ciclo in $G$, ma ricordiamo che può fare una sola delle due domande ad ogni mano, e che Peggy utilizza ogni volta un nuovo $H$: 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 $G$ dall'informazione che riceve in ogni mano da Peggy.

Se Peggy non conosce l'informazione, può al più generare o un grafo isomorfo a $G$ ma non un suo ciclo hamiltoniano, oppure un ciclo hamiltoniano per il grafo che ha sottoposto a Victor, che però non sarebbe isomorfo a $G$. 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 $G$ 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 $2^{-n}$, dove $n$ è 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).
• Parliamo di conoscenza zero algoritmica se non v'è algoritmo efficiente (tipicamente che corre in tempo polinomiale all'input) capace di distinguere le due distribuzioni di probabilità.

Storia e risultati

Le dimostrazioni conoscenza zero furono originariamente concepite nel 1985 da Shafi Goldwasser, et al., in una bozza di "The knowledge complexity of interactive proof-systems". Nonostante tale rilevante pubblicazione non abbia inventato i sistemi di dimostrazione interattivi, ha per la prima volta proposto la gerarchia "IP" nell'ambito di questi (concetto di interactive system proof) e concepito il concetto di "complessità conoscitiva", una misura della quantità di conoscenza circa una dimostrazione trasferita dal dimostratore al verificatore. Gli autori diedero anche la prima dimostrazione conoscenza zero per un problema concreto, decidere i nonresidui quadratici mod "m". Citando (considerando dimostrazione come sinonimo di algoritmo):

Di particolare interesse è il caso dove questa conoscenza addizionale è essenzialmente 0 e mostriamo che è possibile dimostrare interattivamente che un numero è nonresiduo quadratico mod "m" rilasciando conoscenza addizionale 0. Ciò è sorprendente giacché non c'è algoritmo efficiente capace di decidere circa i residui modulo "m" quando la fattorizzazione di "m" non è data. Inoltre, tutte le dimostrazioni "NP" per il problema esibiscono la fattorizzazione prima di "m". Questo indica che aggiungere interazione al processo di dimostrazione può decrementare la quantità d'informazione che dev' essere comunicata per dimostrare un teorema.

Il problema in oggetto ha sia un algoritmo risolutivo NP sia uno co-NP, è all'intersezione tra le due classi, e lo stesso vale per molti altri problemi per cui si sono scoperte successivamente dimostrazioni conoscenza zero (ad esempio).

Oded Goldreich, et al., hanno portato il discorso ad un livello ancora superiore mostrando che, assumendo l'esistenza di una crittatura inattaccabile, si può costruire una prova conoscenza zero per il problema NP-completo della colorazione di un grafo a tre colori. Poiché ogni problema in NP può essere efficientemente ridotto a questo problema, ciò significa che, sotto tale assunzione, tutti i problemi in NP possono avere dimostrazioni conoscenza zero (cioè ancora algoritmi risolutivi;). La motivazione per l'assunzione è che, come nell'esempio di sopra, i loro protocolli richiedono cifratura. Una situazione sufficiente comunemente citata per l'esistenza di una crittografia invincibile è l'esistenza di funzioni ad una via (ossia facili da calcolare su qualsiasi input ma difficili, in termini computazionali, da invertire datane un'immagine), ma è concepibile che un qualche mezzo fisico possa raggiungerla di per sé.

Inoltre, hanno anche dimostrato che il problema complemento dell'isomorfismo tra grafi ha una dimostrazione conoscenza zero; tale problema è in co-NP al momento, ma non si sa se sia in NP o in una qualche altra classe pratica. Più in generale, Goldreich, Goldwasser et al. hanno anche provato che, anche assumendo tale cifratura teorica, vi sono dimostrazioni conoscenza zero per "tutti" i problemi in IP=PSPACE, o in altre parole, tutto quel che può essere dimostrato da un sistema interattivo può esserlo da uno a conoscenza zero.

Preferendo non fare assunzioni non necessarie, molti studiosi hanno intravisto modi per eliminare la necessità di funzioni ad una via. Tra gli altri, uno è stato tramite "sistemi di dimostrazione interattivi multipli" i quali hanno molti dimostratori indipendenti invece di uno solo, permettendo al verificatore di esaminare in modo incrociato i singoli prover singolarmente per evitare di essere fuorviato. Si può dimostrare che, senza assunzioni d'intrattabilità, tutti i linguaggi in NP hanno dimostrazioni conoscenza zero in un sistema del genere.

Salta all'occhio che in uno scenario come quello di Internet, dove più protocolli possono essere eseguiti concorrentemente, costruire prove conoscenza zero è più interessante. La linea di ricerca che investiga dimostrazioni conoscenza zero concorrenti fu iniziata dai lavori di Dwork, Naor e Sahai. Un particolare sviluppo lungo questa è stata lo sviluppo di protocolli cosiddetti witness-indistinguishable. La proprietà è legata a quella delle conoscenza zero, ma tali protocolli non soffrono degli stessi problemi di esecuzione concorrente.

Le dimostrazioni a conoscenza zero possono essere in un'altra variante anche non interattive. Blum, Feldman, e Micali hanno mostrato che una stringa casuale condivisa tra il dimostratore ed il verificatore è abbastanza per raggiungere il caso computazionale della conoscenza zero, senza richiedere interazione.

Collegamenti esterni

• (EN) Applied Kid Cryptography – Una semplice spiegazione delle dimostrazioni a conoscenza zero
• (EN) Come costruire sistemi di dimostrazione a conoscenza zero per sistemi NP, su wisdom.weizmann.ac.il.
• (EN) An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products, su cs.ucsd.edu.
• (EN) Un tutorial di Oded Goldreich sulle dimostrazioni a conoscenza zero, su wisdom.weizmann.ac.il.
• (EN) tesi di dottorato di Salil Vadhan sulla conoscenza zero statistica, su eecs.harvard.edu. URL consultato il 27 aprile 2008 (archiviato dall'url originale il 10 marzo 2009).