Dimostrazione a conoscenza zero: differenze tra le versioni

In [[crittografia]] una '''dimostrazione a conoscenza zero''' o ''' protocollo a conoscenza zero''' è un metodo interattivo 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.

|[[ImmagineFile:Zkip alibaba1.png|150px]]

|[[ImmagineFile:Zkip alibaba2.png|150px]]

|[[ImmagineFile:Zkip alibaba3.png|150px]]

C'e'è una storia ben conosciuta per presentare alcune delle idee alla base della dimostrazione a conoscenza zero, pubblicata inizialmente da [[Jean-Jacques Quisquater]] ed altri nel loro articolo "Come spiegare i Protocolli a Conoscenza-Zero ai vostri figli".<ref>Jean-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. [http://www.cs.wisc.edu/~mkowalcz/628.pdf pdf]</ref>.

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 finoprima a quandodi saràessere sicuro che lei lo conosca veramentedavvero. Peggy si dice ched'accordo glia diràrivelargli il segreto, ma non prima di ricevereaver ricevuto i soldi. Pianificano quindi uno schema con il quale Peggy può provaredare prova a Victor di conoscere la parola senza dichiararla a Victorrivelargliela.

PrimaDapprima, 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 truccoespediente molte volte, diciamo(ad esempio, venti volte una dopo l'altra), l'opportunitàla possibilità per Peggy di anticipareadempiere correttamentein modo corretto, senza conoscere davvero la parola magica, a tutte le richieste di Victor, diventerebbe statisticamente molto piccola (in virtù della [[indipendenza stocastica|probabilità]] di eventi indipendenti]]).

# '''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.

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".

Una definizione formale di dimostrazione a conoscenza zero deve usare un qualche modello di computazione, il principeprincipale è 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

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 di[[Shafi GoldreichGoldwasser]], [[Silvio Micali]], e WigdersonCharles Rackoff, sulla computazione sicura multiparte.

== Un esempioEsempio concreto ==

* All'inizio di ogni mano, Peggy crea "<math>H"</math>, un [[Isomorfismo#Grafi|grafo isomorfo]] a "<math>G"</math>, e lo sottopone a Victor. Poiché è trivialebanale tradurre un ciclo hamiltoniano tra grafi dato un isomorfismo (ossia è possibile trovare, a partire dal ciclo hamiltoniano di "<math>H"</math> e da un suo isomorfismo per "<math>G"</math>, il ciclo hamiltoniano corrispondente in "<math>G"</math>, e vale anche il caso duale), se Peggy conosce un ciclo hamiltoniano per "<math>G"</math> ne conosce anche uno per "<math>H"</math>.

* Victor sceglie poi a caso una delle due seguenti domande da porre a Peggy. Può chiederle di mostrare l'isomorfismo tra "<math>H"</math> e "<math>G"</math> oppure può richiederle di mostrare un hamiltoniano in "<math>H"</math>.

* Nel primo caso, Peggy fornisce le traduzioni di vertice che mappano "<math>G"</math> in "<math>H"</math> (in pratica, applica l'isomorfismo). Victor può certamente verificare che i due siano isomorfi.

* Nel secondo caso, Peggy traduce il suo ciclo hamiltoniano di "<math>G"</math> nel corrispondente in "<math>H"</math> 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 "<math>H"</math>. Perciò, alfineper d'essere in grado di rispondere correttamente ad entrambeognuna delle due possibili richieste, "<math>H"</math> dev'essere isomorfo a "<math>G"</math> e Peggy deve avere un ciclo hamiltoniano in "<math>H"</math>. Poiché solo un dimostratore a conoscenza di un ciclo hamiltoniano in "<math>G"</math> 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 "<math>G"</math>.

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

Se Peggy non conosce l'informazione, può provareal adpiù indovinaregenerare qualeo domandaun Victorgrafo leisomorfo chiederàa e<math>G</math> generarema onon un suo ciclo hamiltoniano, oppure un ciclo hamiltoniano per il grafo che ha sottoposto a Victor, che però non sarebbe isomorfo a "<math>G"</math>. oIn unentrambi i casi Victor ha la possibilità di rivolgere a Peggy una domanda che la smaschera: nel primo caso chiedendole di mostrare il ciclo hamiltoniano per undel grafo genericoproposto, manel poichésecondo noncaso chiedendole di conoscemostrare l'informazioneisomorfismo stessatra non<math>G</math> puòe fareil entrambegrafo proposto. ConLe questoprobabilità indovinìo,che leha suePeggy probabilitàdi d'imbrogliareriuscire ad ingannare Victor, ovvero di evitare ad ogni mano la domanda che la smaschererebbe, sono pari a 2<sup >&minus;<var math>2^{-n}</var ></sup math>, dove <var math>n</var math> è il numero di mani. Per tutti gli usi pratici, è infattibile il battere una dimostrazione conoscenza zero con un numero di mani ragionevole a garanzia.

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. CioCiò è 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 (complessità)|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 <ref>Oded Goldreich. A zero-knowledge proof that a two-prime moduli is not a Blum integer. Unpublished manuscript. 1985.</ref>).

[[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;<ref>Oded Goldreich, Silvio Micali, Avi Wigderson. [httphttps://portal.acm.org/citation.cfm?id=116852 Proofs that yield nothing but their validity]. ''Journal of the ACM'', volume 38, issue 3, p.690-728. July 1991.</ref>).

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<ref>Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Hastad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. S. Goldwasser, editor. In ''Advances in Cryptology--CRYPTO '88'', volume 403 of ''Lecture Notes in Computer Science'', p.37-56. Springer-Verlag, 1990, 21-25. August 1988.</ref>.

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<ref>M. Ben-or, Shafi Goldwasser, J. Kilian, and A. Wigderson. [http://theory.lcs.mit.edu/~cis/pubs/shafi/1988-stoc-bgkw.pdf Multi prover interactive proofs: How to remove intractability assumptions]. ''Proceedings of the 20th ACM Symposium on Theory of Computing'', p.113-121. 1988.</ref>.

Le provedimostrazioni a conoscenza zero possono essere in un' altra variante anche non interattive. Blum, Feldman, e Micali <ref>Manuel Blum, Paul Feldman, and Silvio Micali. Non-Interactive Zero-Knowledge and Its Applications. Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC 1988). 103-112. 1988</ref> 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.

* {{en}}cita [web|http://www.wisdom.weizmann.ac.il/~oded/gmw1.html |Come costruire sistemi di dimostrazione a conoscenza zero per sistemi NP]|lingua=en}}

* {{en}}cita [web|http://www.cs.ucsd.edu/users/daniele/papers/GMR.html |An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products]|lingua=en}}

* {{en}}cita [web|http://www.wisdom.weizmann.ac.il/~oded/zk-tut02.html |Un tutorial di Oded Goldreich sulle dimostrazioni a conoscenza zero]|lingua=en}}

* {{en}}cita [web|1=http://www.eecs.harvard.edu/~salil/papers/phdthesis-abs.html |2=tesi di dottorato di Salil Vadhan sulla conoscenza zero statistica]|lingua=en|accesso=27 aprile 2008|urlarchivio=https://web.archive.org/web/20090310115551/http://www.eecs.harvard.edu/~salil/papers/phdthesis-abs.html#|dataarchivio=10 marzo 2009|urlmorto=sì}}