Demonstrație de cunoaștere zero

În criptografie, un protocol zero-knowledge proof sau zero-knowledge protocol este o metodă interactivă utilizată de un subiect pentru a demonstra unui alt subiect că o afirmație (de obicei matematică) este adevărată, fără a dezvălui altceva decât veridicitatea sa.

Exemplu abstract

Există o poveste binecunoscută care prezintă unele dintre ideile din spatele dovezii de cunoaștere zero ^[1] . Este obișnuit să numim cele două părți într-o dovadă fără cunoștințe Peggy (care dovedește cererea) și Victor (care verifică cererea).

În această poveste, Peggy a descoperit cuvântul secret folosit pentru a deschide ușa magică într-o peșteră. Peștera are forma unui cerc, cu intrarea pe o parte și ușa magică care blochează cealaltă parte. Victor spune că o va plăti pentru secret, dar nu înainte de a fi sigur că îl cunoaște cu adevărat. Peggy este de acord să dezvăluie secretul, dar nu înainte de a primi banii. Ei planifică apoi un model prin care Peggy îi poate demonstra lui Victor că știe cuvântul fără să-l dezvăluie.

La început, Victor așteaptă în afara peșterii când Peggy intră. Etichetăm calea stângă și dreaptă începând de la intrare cu A și B. Peggy alege aleatoriu una dintre cele două căi. Apoi, Victor intră în peșteră și strigă numele cărării pe care Peggy va trebui să o folosească pentru a se întoarce, între A și B, luată la întâmplare. Dacă se presupune că ea cunoaște cu adevărat cuvântul magic, este ușor: deschideți ușa, dacă este necesar, și reveniți pe calea dorită. Trebuie remarcat faptul că Victor nu cunoaște calea pe care a intrat Peggy.

Oricum, să presupunem că Peggy nu știe cuvântul. Apoi, ar putea reveni prin calea numită dacă Victor ar fi ales numele aceleiași căi pe care a intrat-o. Din moment ce Victor a ales A sau B la întâmplare, el ar avea 50% șanse să ghicească corect. Dacă cei doi ar repeta acest lucru de multe ori (de exemplu, de douăzeci de ori unul după altul), posibilitatea ca Peggy să îndeplinească corect toate cererile lui Victor, fără să cunoască cu adevărat cuvântul magic, ar deveni statistic foarte mică (în virtutea probabilității de evenimente independente ).

Prin urmare, dacă Peggy apare „fiabil” la ieșirea lui Victor, aceasta poate concluziona că cel mai probabil știe cu adevărat cuvântul secret.

Definiție

O dovadă de cunoaștere zero trebuie să îndeplinească trei proprietăți:

Completitudine : dacă afirmația este adevărată, un demonstrant onest va putea convinge un verificator onest (adică care urmează protocolul exact) de fapt.
Corectitudine : dacă afirmația este falsă, nici un demonstrant înșelător nu va putea convinge verificatorul onest că este adevărat, sau mai degrabă probabilitatea de a-l putea convinge poate fi redusă la dorință.
Cunoștințe zero : dacă afirmația este adevărată, niciun verificator de înșelăciune nu va ști altceva decât acele informații. Acest fapt este formalizat prin arătarea că fiecare verificator de înșelăciune poate fi asociat cu un simulator care, dacă i se oferă doar pretenția de a demonstra (și nu are acces la dovadă), poate obține o transcriere care „arată” ca o interacțiune între dovada onestă. și verificatorul de înșelăciune.

Primele două sunt proprietățile clasei mai generale de sisteme interactive de probă; al treilea este specific dovezilor zero-cunoștințe. În special, prima caracteristică răspunde la completitudinea înțeleasă în mod obișnuit în logică („adevărul este derivabil”, informal), în timp ce a doua nu este direct legată de corectitudine (pentru care „derivabilul este adevărat”: de fapt, corectitudinea unui dovada interactivă este definită la fel ca mai sus și este diferită de noțiunea obișnuită de soliditate ); componenta esențială este evident a treia.

Cercetările în domeniul dovezilor fără cunoaștere au fost promovate de sisteme de autentificare în care o parte dorește să-și demonstreze identitatea unei a doua părți prin intermediul unor informații secrete (cum ar fi o parolă), dar dorește ca partea a doua să nu știe nimic din acest secret . Aceasta se numește „dovadă de cunoaștere zero-cunoștință”.

Dovezile de cunoaștere zero nu sunt dovezi în sens matematic, deoarece există întotdeauna o mică șansă ca o dovadă înșelătoare să poată convinge un verificator de o afirmație falsă. Cu alte cuvinte, aceste tipuri de algoritmi sunt probabilistici și nedeterministe. Cu toate acestea, există tehnici pentru a reduce această probabilitate la valori mici după bunul plac.

O definiție formală a dovezii de cunoaștere zero trebuie să utilizeze un model de calcul, principalul fiind mașina Turing . Fie P , V și S mașinile Turing. Un sistem interactiv de probă cu (P, V) cu un limbaj L este zero-cunoaștere dacă pentru fiecare verificator probabilistic de timp polinomial (PPT) există un simulator PPT de S astfel încât

 $\forall x\in L,z\in \{0,1\}^{*},View_{\hat {V}}[P(x)\leftrightarrow {\hat {V}}(x,z)]=S(x,z)$  $\forall$   $X$   $\in$   $L$   $,$   $z$   $\in$   ${$   $0$   $,$   $1$   $}$   $*$   $,$   $V.$   $the$   $Și$   $w$   $V.$   $^$   $[$   $P.$   $($   $X$   $)$   $\leftrightarrow$   $V.$   $^$   $($   $X$   $,$   $z$   $)$   $]$   $=$   $S.$   $($   $X$   $,$   $z$   $)$   ${\ displaystyle \ forall x \ in L, z \ in \ {0,1 \} ^ {*}, View _ {\ hat {V}} [P (x) \ leftrightarrow {\ hat {V}} (x , z)] = S (x, z)}$   $\ forall x \ in L, z \ in \ {0, 1 \} ^ {*}, View _ {\ hat V} [P (x) \ leftrightarrow \ hat V (x, z)] = S (x, z)$

Dovada P este modelată ca având o putere de calcul nelimitată (în practică P este de obicei o mașină probabilistică de Turing ). Intuitiv, definiția afirmă că un sistem interactiv de probă ( P , V ) este zero-cunoștință dacă pentru fiecare verificator ${\hat {V}}$ ${\ displaystyle {\ hat {V}}}$ ${\ hat V}$ există un simulator S eficient care poate reproduce conversația dintre P și ${\hat {V}}$ ${\ displaystyle {\ hat {V}}}$ ${\ hat V}$ pentru fiecare intrare dată. Șirul auxiliar z din definiție joacă rolul de „cunoștințe anterioare”. Definiția implică asta ${\hat {V}}$ ${\ displaystyle {\ hat {V}}}$ ${\ hat V}$ nu poate folosi niciun șir cunoscut a priori pentru a afla informații despre conversația cu P, deoarece cere că, dacă lui S i se oferă și aceste cunoștințe a priori, atunci acesta poate reproduce conversația dintre ${\hat {V}}$ ${\ displaystyle {\ hat {V}}}$ ${\ hat V}$ și P ca înainte.

Definiția dată este cea a cunoașterii zero perfecte. Cunoștințele de calcul zero sunt obținute prin necesitatea vizualizărilor verificatorului ${\hat {V}}$ ${\ displaystyle {\ hat {V}}}$ ${\ hat V}$ și a simulatorului (adică a lui Victor și, respectiv, a lui Peggy) sunt indistincte numai din punct de vedere calculatic , având în vedere șirul auxiliar.

Cu toate acestea, o parolă este de obicei prea scurtă sau insuficient aleatorie pentru a fi utilizată în multe scheme de demonstrație fără cunoștințe. O dovadă de cunoaștere zero a parolelor este un tip special de dovadă de cunoaștere zero, care este specifică parolelor cu lungime limitată.

Una dintre cele mai fascinante utilizări ale dovezilor zero-cunoștințe în protocoalele criptografice este de a impune un comportament onest menținând în același timp confidențialitatea. Apropo, ideea este de a forța utilizatorul să demonstreze, folosind o dovadă de zero cunoștințe, corectitudinea comportamentului său față de protocol. Datorită corectitudinii, știm că utilizatorul trebuie să se comporte cu adevărat sincer pentru a putea furniza o dovadă validă. Și din cauza cunoștințelor zero, știm că utilizatorul nu compromite confidențialitatea secretelor lor în procesul de furnizare a dovezilor. Această aplicație a dovezilor zero-cunoștințe a fost folosită pentru prima dată în publicația șocantă Shafi Goldwasser, Silvio Micali și Charles Rackoff, privind calculul multipart securizat.

Exemplu concret

Putem extinde aceste concepte la o aplicație criptografică mai realistă. În acest scenariu, Peggy cunoaște un ciclu hamiltonian pentru un grafic mare $G.$ ${\ displaystyle G}$ $G.$ . Victor știe $G.$ ${\ displaystyle G}$ $G.$ dar nu ciclul (de exemplu, Peggy a dat naștere $G.$ ${\ displaystyle G}$ $G.$ și i l-a dezvăluit.) Peggy va încerca să cunoască ciclul fără să-l dezvăluie. Un ciclu hamiltonian într-un grafic este doar o modalitate de implementare a dovezii de cunoaștere zero; de fapt, orice problemă NP-completă poate fi utilizată în acest scop, precum și un alt tip de problemă dificilă, cum ar fi factorizarea ^[2] . Cu toate acestea, Peggy nu vrea doar să-i dezvăluie hamiltonianului sau orice altă informație lui Victor; vrea să păstreze ciclul secret (poate că Victor este interesat să îl cumpere, dar vrea mai întâi un cec sau poate Peggy este singurul care cunoaște aceste informații și își dovedește identitatea lui Victor).

Pentru a arăta că știe ciclul, Peggy joacă alături de Victor după cum urmează:

La începutul fiecărei mâini, Peggy creează $H.$ ${\ displaystyle H}$ $H.$ , un grafic izomorf a $G.$ ${\ displaystyle G}$ $G.$ , și o înaintează lui Victor. Deoarece este banal să se traducă un ciclu hamiltonian între grafice date unui izomorfism (adică este posibil să se găsească, pornind de la ciclul hamiltonian al $H.$ ${\ displaystyle H}$ $H.$ iar din izomorfismul său pentru $G.$ ${\ displaystyle G}$ $G.$ , ciclul hamiltonian corespunzător în $G.$ ${\ displaystyle G}$ $G.$ , iar cazul dual se menține), dacă Peggy cunoaște un ciclu hamiltonian pentru $G.$ ${\ displaystyle G}$ $G.$ știe și unul pentru $H.$ ${\ displaystyle H}$ $H.$ .
Victor alege apoi aleatoriu una dintre următoarele două întrebări pe care să le adreseze lui Peggy. Îi puteți cere să arate izomorfismul dintre $H.$ ${\ displaystyle H}$ $H.$ Și $G.$ ${\ displaystyle G}$ $G.$ sau poate fi necesar să arate un hamiltonian în $H.$ ${\ displaystyle H}$ $H.$ .
În primul caz, Peggy oferă traducerile de vârf pe care le mapează $G.$ ${\ displaystyle G}$ $G.$ în $H.$ ${\ displaystyle H}$ $H.$ (practic, aplicați izomorfism). Victor poate verifica cu siguranță că cele două sunt izomorfe.
În al doilea caz, Peggy își traduce ciclul hamiltonian de $G.$ ${\ displaystyle G}$ $G.$ în corespunzătorul în $H.$ ${\ displaystyle H}$ $H.$ și o dezvăluie lui Victor. Apoi verifică validitatea acestuia.

Cu fiecare mână, Peggy nu știe ce cerere i se va face până nu îi va da lui Victor graficul $H.$ ${\ displaystyle H}$ $H.$ . Prin urmare, pentru a putea răspunde corect la fiecare dintre cele două solicitări posibile, $H.$ ${\ displaystyle H}$ $H.$ trebuie să fie izomorfă a $G.$ ${\ displaystyle G}$ $G.$ iar Peggy trebuie să aibă un ciclu hamiltonian în $H.$ ${\ displaystyle H}$ $H.$ . Din moment ce doar un demonstrant conștient de un ciclu hamiltonian în $G.$ ${\ displaystyle G}$ $G.$ poate fi întotdeauna capabil să răspundă la ambele solicitări, Victor (după un număr suficient de mâini, datorită naturii probabilistice a procedurii), este convins că Peggy cunoaște informațiile, adică un ciclu hamiltonian în $G.$ ${\ displaystyle G}$ $G.$ .

Cu toate acestea, răspunsul lui Peggy așa cum îl vedem nu dezvăluie aceste informații. Cu fiecare mână, Victor va afla doar despre izomorfism din $H.$ ${\ displaystyle H}$ $H.$ în $G.$ ${\ displaystyle G}$ $G.$ sau a unui hamiltonian în $H.$ ${\ displaystyle H}$ $H.$ . Ar avea nevoie de ambele informații pentru una anume $H.$ ${\ displaystyle H}$ $H.$ pentru a afla ciclul din $G.$ ${\ displaystyle G}$ $G.$ , dar nu uitați că poate pune doar una dintre cele două întrebări din fiecare mână și că Peggy folosește una nouă de fiecare dată $H.$ ${\ displaystyle H}$ $H.$ : informațiile rămân necunoscute tocmai în virtutea acestei ultime condiții, odată ce prima a fost stabilită ca regula neschimbabilă a jocului.

Datorită naturii izomorfismelor dintre grafice și ciclurile hamiltoniene, Victor nu are câștig de informații despre ciclul hamiltonian în $G.$ ${\ displaystyle G}$ $G.$ din informațiile pe care le primește în fiecare mână de la Peggy.

Dacă Peggy nu cunoaște informațiile, poate genera cel mult un grafic izomorf a $G.$ ${\ displaystyle G}$ $G.$ dar nu un ciclu hamiltonian al său sau un ciclu hamiltonian pentru graficul pe care i l-a prezentat lui Victor, care totuși nu ar fi izomorf $G.$ ${\ displaystyle G}$ $G.$ . În ambele cazuri, Victor are posibilitatea de a-i pune lui Peggy o întrebare care o demască: în primul caz cerându-i să arate ciclul hamiltonian al graficului propus, în al doilea caz cerându-i să arate izomorfismul dintre $G.$ ${\ displaystyle G}$ $G.$ și graficul propus. Probabilitățile pe care le are Peggy de a-l putea înșela pe Victor sau de a evita întrebarea care ar fi demascată la fiecare mână sunt egale cu $2^{-n}$ ${\ displaystyle 2 ^ {- n}}$ ${\ displaystyle 2 ^ {- n}}$ , unde este $n$ ${\ displaystyle n}$ $n$ este numărul de mâini. Pentru toate utilizările practice, este într-adevăr fezabil să învingem o demonstrație cu cunoștințe zero, cu un număr rezonabil de mâini de garantat.

Variante ale modelului

Diferite variante ale dovezii de cunoaștere zero pot fi definite prin formalizarea conceptului intuitiv a ceea ce se înțelege prin ieșirea simulatorului „arată ca” execuția protocolului actual menționat mai sus:

Vorbim de cunoștințe zero perfect dacă cele două distribuții asociate simulatorului și protocolului demonstrativ sunt exact aceleași; acesta este cazul primului exemplu.
Vorbim de cunoștințe statistice zero dacă distribuțiile nu sunt neapărat egale, ci sunt apropiate statistic, ceea ce înseamnă că diferența lor statistică este neglijabilă (în mod informal, ne putem gândi la o metrică între distribuțiile avute în vedere pentru a evalua această diferență).
Vorbim de cunoștințe algoritmice zero dacă nu există un algoritm eficient (de obicei rulează în timp polinomial la intrare) capabil să distingă cele două distribuții de probabilitate.

Istorie și rezultate

Zero dovezi de cunoaștere au fost concepute inițial în 1985 de Shafi Goldwasser și colab., Într-un proiect al „Complexității cunoașterii sistemelor de probă interactive” ^[3] . Deși această publicație relevantă nu a inventat sisteme interactive de demonstrație, a propus pentru prima dată ierarhia „IP” în cadrul acestora (conceptul de dovadă a sistemului interactiv ) și a conceput conceptul de „complexitate cognitivă”, o măsură a cantității de cunoștințe despre o dovadă transferat de la demonstrant la verificator. Autorii au oferit, de asemenea, prima dovadă a cunoașterii zero pentru o problemă concretă, decidând mod rezidual pătratic mod "m" . Citarea (considerând dovada ca sinonim pentru algoritm):

Un interes deosebit este cazul în care această cunoaștere suplimentară este în esență 0 și arătăm că este posibil să se demonstreze interactiv că un număr este mod pătratic nereziduu "eliberând" cunoștințe suplimentare 0. Acest lucru este surprinzător deoarece nu există un algoritm eficient capabil să deciderea despre reziduuri modulo "m" atunci când factorizarea lui "m" nu este dată. De asemenea, toate dovezile „NP” pentru problemă prezintă factorizarea înaintea „m”. Acest lucru indică faptul că adăugarea interacțiunii la procesul de probă poate reduce cantitatea de informații care trebuie comunicate pentru a demonstra o teoremă.

Problema în cauză are atât un NP și un co-NP algoritm de rezolvare, este la intersecția dintre cele două clase, și același lucru este valabil și pentru multe alte probleme pentru care la zero dovezi de cunoștințe au fost descoperite mai târziu (de exemplu , ^[4] ).

Oded Goldreich, și colab., Au dus discuția la un nivel și mai înalt arătând că, presupunând existența unei criptări inatacabile, se poate construi o dovadă de cunoaștere zero pentru problema completă a NP a colorării unui grafic în trei culori. Deoarece fiecare problemă din NP poate fi redusă eficient la această problemă, aceasta înseamnă că, sub această ipoteză, toate problemele din NP pot avea zero dovezi de cunoaștere (adică algoritmi de rezolvare totuși; ^[5] ). Rațiunea ipotezei este că, la fel ca în exemplul de mai sus, protocoalele lor necesită criptare. O situație suficientă citată în mod obișnuit pentru existența criptografiei invincibile este existența funcțiilor unidirecționale (adică ușor de calculat pe orice intrare, dar dificil, în termeni de calcul, de inversare dată unei imagini), dar este de conceput că un anumit mijloc fizic o poate realiza de la sine.

Mai mult, au demonstrat, de asemenea, că problema complementară a izomorfismului dintre grafice are o dovadă de cunoaștere zero; o astfel de problemă este în co-NP în acest moment, dar nu se știe dacă este în NP sau în altă clasă practică. Mai general, Goldreich, Goldwasser și colab. au dovedit, de asemenea, că, chiar presupunând această criptare teoretică, există zero dovezi de cunoaștere pentru „toate” problemele din IP = PSPACE sau, cu alte cuvinte, orice poate fi dovedit de un sistem interactiv poate fi dovedit de unul cu zero cunoștințe ^{[6 ]} .

Preferând să nu facă presupuneri inutile, mulți cercetători au văzut modalități de a elimina necesitatea funcțiilor unidirecționale. Printre altele, unul a fost prin „sisteme multiple de probă interactivă”, care au multe dovezi independente în loc de una singură, permițând verificatorului să interogheze individual proveri individuali pentru a evita să fie indus în eroare. Se poate arăta că, fără ipoteze de intratabilitate, toate limbile din NP au zero dovezi de cunoaștere într-un astfel de sistem ^[7] .

Este evident că într-un scenariu precum Internetul , în care mai multe protocoale pot rula concomitent , construirea unor dovezi de cunoaștere zero este mai interesantă. Linia de cercetare care investighează demonstrațiile concurente de cunoștințe zero a fost inițiată de lucrările lui Dwork, Naor și Sahai ^[8] . O evoluție specială de-a lungul acestui fapt a fost dezvoltarea așa - numitelor protocoale care nu pot fi distinse de martori . Proprietatea este legată de cea a cunoașterii zero, dar astfel de protocoale nu suferă de aceleași probleme de execuție concurente. ^[9]

Dovezile zero-cunoștințe pot fi, de asemenea, non-interactive într-o altă variantă. Blum, Feldman și Micali ^[10] au arătat că un șir aleatoriu împărțit între dovadă și verificator este suficient pentru a ajunge la cazul de calcul al cunoașterii zero, fără a necesita interacțiune.

Notă

^ Jean-Jacques Quisquater, Louis C. Guillou, Thomas A. Berson. Cum să explici copiilor tăi protocoalele de cunoaștere zero. Progresele în criptologie - CRYPTO '89: Proceedings , v.435, p.628-631, 1990. pdf
^ Explicația bsy a dovezilor de cunoaștere zero
^ Shafi Goldwasser, Silvio Micali și Charles Rackoff. Complexitatea cunoștințelor sistemelor de probă interactive . Lucrările celui de-al 17-lea Simpozion privind teoria calculului , Providence, Rhode Island. 1985. Proiect. Rezumat extins
^ Oded Goldreich. O dovadă de cunoaștere zero că un modulo cu două prime nu este un întreg Blum. Manuscris nepublicat. 1985.
^ Oded Goldreich, Silvio Micali, Avi Wigderson. Dovezi care nu dau altceva decât validitatea lor . Jurnalul ACM , volumul 38, numărul 3, p.690-728. Iulie 1991.
^ Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Hastad, Joe Kilian, Silvio Micali și Phillip Rogaway. Tot ceea ce poate fi demonstrat este demonstrabil în cunoașterea zero. S. Goldwasser, editor. În Advances in Cryptology - CRYPTO '88 , volumul 403 din Lecture Notes in Computer Science , p.37-56. Springer-Verlag, 1990, 21-25. August 1988.
^ M. Ben-or, Shafi Goldwasser, J. Kilian și A. Wigderson. Dovezi interactive multiple: cum se elimină ipotezele de intractabilitate . Proceedings of the 20th ACM Symposium on Theory of Computing , p.113-121. 1988.
^ Cynthia Dwork, Moni Naor și Amit Sahai. Cunoștințe zero concurente. Jurnalul ACM ( JACM ) , v.51 nr.6, p.851-898, noiembrie 2004.
^ Uriel Feige și Adi Shamir. Protocoale de identificare a martorilor și ascunderea martorilor. „Simpozionul ACM pe teoria calculelor (STOC)”, 1990
^ Manuel Blum, Paul Feldman și Silvio Micali. Cunoștințe zero interactive și aplicațiile sale. Lucrările celui de-al douăzecilea simpozion anual ACM pe teoria calculelor (STOC 1988). 103-112. 1988

linkuri externe

(EN) Applied Cryptography Kid - O explicație simplă a dovezilor fără cunoștințe
( EN ) Cum să construiți sisteme de probă zero-cunoștințe pentru sistemele NP , la wise.weizmann.ac.il .
( EN )Un sistem statistic non-interactiv eficient, fără dovezi de cunoaștere zero pentru produse prime cvasi-sigure , su cs.ucsd.edu .
( EN )Un tutorial de Oded Goldreich privind dovezile decunoaștere zero , pe înțelepciunea.weizmann.ac.il .
( EN ) Teza de doctorat a lui Salil Vadhan despre cunoașterea statistică zero , pe eecs.harvard.edu . Accesat la 27 aprilie 2008 (arhivat din original la 10 martie 2009) .

Portal de criptografie : Accesați intrările Wikipedia care se ocupă de criptografie

[1] Jean-Jacques Quisquater, Louis C. Guillou, Thomas A. Berson. Cum să explici copiilor tăi protocoalele de cunoaștere zero. Progresele în criptologie - CRYPTO '89: Proceedings , v.435, p.628-631, 1990. pdf

[2] Explicația bsy a dovezilor de cunoaștere zero

[3] Shafi Goldwasser, Silvio Micali și Charles Rackoff. Complexitatea cunoștințelor sistemelor de probă interactive . Lucrările celui de-al 17-lea Simpozion privind teoria calculului , Providence, Rhode Island. 1985. Proiect. Rezumat extins

[4] Oded Goldreich. O dovadă de cunoaștere zero că un modulo cu două prime nu este un întreg Blum. Manuscris nepublicat. 1985.

[5] Oded Goldreich, Silvio Micali, Avi Wigderson. Dovezi care nu dau altceva decât validitatea lor . Jurnalul ACM , volumul 38, numărul 3, p.690-728. Iulie 1991.

[6] Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Hastad, Joe Kilian, Silvio Micali și Phillip Rogaway. Tot ceea ce poate fi demonstrat este demonstrabil în cunoașterea zero. S. Goldwasser, editor. În Advances in Cryptology - CRYPTO '88 , volumul 403 din Lecture Notes in Computer Science , p.37-56. Springer-Verlag, 1990, 21-25. August 1988.

[7] M. Ben-or, Shafi Goldwasser, J. Kilian și A. Wigderson. Dovezi interactive multiple: cum se elimină ipotezele de intractabilitate . Proceedings of the 20th ACM Symposium on Theory of Computing , p.113-121. 1988.

[8] Cynthia Dwork, Moni Naor și Amit Sahai. Cunoștințe zero concurente. Jurnalul ACM ( JACM ) , v.51 nr.6, p.851-898, noiembrie 2004.

[9] Uriel Feige și Adi Shamir. Protocoale de identificare a martorilor și ascunderea martorilor. „Simpozionul ACM pe teoria calculelor (STOC)”, 1990

[10] Manuel Blum, Paul Feldman și Silvio Micali. Cunoștințe zero interactive și aplicațiile sale. Lucrările celui de-al douăzecilea simpozion anual ACM pe teoria calculelor (STOC 1988). 103-112. 1988

[1]

[2]

[3]

[4]

[5]

[6 ]

[7]

[8]

[9]

[10]