Vizualizare sursă pentru „Demonstrație fără divulgare de cunoștințe”

În [[criptografie]], o '''demonstrație fără divulgare de cunoștințe''' sau '''un protocol fără divulgare de cunoștințe''' este o metodă prin care o parte (demonstratorul) poate dovedi altei părți (verificatorul) că o anumită afirmație este adevărată, evitând în același timp să transmită verificatorului orice informație ''în plus față de'' de simplu fapt al adevărului afirmației.<ref>{{Citation|last=Aad|first=Imad|title=Zero-Knowledge Proof|date=2023|url=https://doi.org/10.1007/978-3-031-33386-6_6|pages=25–30|editor-last=Mulder|editor-first=Valentin|periodical=Trends in Data Protection and Encryption Technologies|place=Cham|publisher=Springer Nature Switzerland|language=en|doi=10.1007/978-3-031-33386-6_6|isbn=978-3-031-33386-6|access-date=2023-10-13|editor2-last=Mermoud|editor2-first=Alain|editor3-last=Lenders|editor3-first=Vincent|editor4-last=Tellenbach|editor4-first=Bernhard|doi-access=free}}</ref> Intuiția care stă la baza demonstrațiilor fără divulgare de cunoștințe este aceea că este trivial să dovedești deținerea anumitor informații prin simpla dezvăluire a lor; provocarea este de a dovedi această posesie fără a dezvălui informațiile sau orice aspect ale acestora.<ref>{{Citat carte|nume=Goldreich|prenume=Oded|legătură-autor=|titlu=Foundations of Cryptography Volume I|an=2001|url=https://www.cambridge.org/core/books/foundations-of-cryptography/B61B6AD235D2034D511A5FF740415166|locul-publicării=|editură=Cambridge University Press|pagină=184|doi=10.1017/CBO9780511546891|isbn=9780511546891}}</ref>

Având în vedere faptul că ar trebui să se poată genera o demonstrație a unei afirmații ''numai'' atunci când deține anumite informații secrete legate de acea afirmație, verificatorul, chiar și după ce s-a convins de adevărul afirmației, ar trebui totuși să rămână în imposibilitatea de a dovedi afirmația către terți.

În modelul simplu, demonstrațiile netriviale fără divulgare de cunoștințe (adică cele pentru limbaje din afara clasei de complexitate BPP ) necesită interacțiune între demonstrator și verificator.<ref>{{Citat carte|nume=Goldreich|prenume=Oded|legătură-autor=|titlu=Foundations of Cryptography Volume I|an=2001|url=https://www.cambridge.org/core/books/foundations-of-cryptography/B61B6AD235D2034D511A5FF740415166|locul-publicării=|editură=Cambridge University Press|pagină=247|doi=10.1017/CBO9780511546891|isbn=9780511546891}}</ref> Această interacțiune implică de obicei selectarea de către verificator a uneia sau mai multor provocări aleatorii; faptul că aceste provocări sunt aleatorii, împreună cu răspunsurile corecte ale demonstratorului la acestea, în ciuda naturii lor aleatoare, au scopul de a convinge verificatorul că demonstratorul ''deține'' cunoștințele pretinse. Dacă interacțiunea nu ar fi prezentă, atunci verificatorul, după ce a obținut transcrierea de execuție a protocolului, adică singurul mesaj al demonstratorului, ar putea reda acea transcriere unei terțe părți, convingând astfel această terță parte (în mod eronat) că și verificatorul deținea informațiile secrete.

Vorbitorii de [[Limba engleză|limbă engleză]] folosesc abrevierea ''ZKIP'' pentru '''''Zero Knowledge Interactive proof'''''.

În modelele obișnuite ale șirurilor aleatoare și ale oracolului aleatoriu, există și demonstrații non-interactive fără divulgare de cunoștințe, drept consecință a euristicii Fiat-Shamir.<ref>{{Citat carte|nume=Goldreich|prenume=Oded|legătură-autor=|titlu=Foundations of Cryptography Volume I|an=2001|url=https://www.cambridge.org/core/books/foundations-of-cryptography/B61B6AD235D2034D511A5FF740415166|locul-publicării=|editură=Cambridge University Press|pagină=299|doi=10.1017/CBO9780511546891|isbn=9780511546891}}</ref><ref name="noninteractive">{{Citat carte|prenume=Manuel|nume=Blum|prenume2=Paul|nume2=Feldman|prenume3=Silvio|nume3=Micali|titlu=Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88|capitol=Non-interactive zero-knowledge and its applications|dată=1988|pagini=103–112|an=1988|doi=10.1145/62212.62222|url=https://apps.dtic.mil/sti/pdfs/ADA222698.pdf|isbn=978-0897912648|data-accesării=June 2, 2022}}</ref><ref name="noninteractive2">{{Citat revistă|nume=Wu|nume2=Wang|prenume=Huixin|prenume2=Feng|dată=2014|titlu=A Survey of Noninteractive Zero Knowledge Proof System and Its Applications|journal=The Scientific World Journal|volum=2014|pagini=560484|pmid=24883407|pmc=4032740|doi=10.1155/2014/560484}}</ref> În practică, aceste demonstrații se bazează pe ipoteze de calcul (de obicei, rezistența la coliziune a unei [[Funcție hash|funcții hash]] criptografice ).

== Exemple abstracte ==

=== Peștera lui Ali Baba ===
{{Imagine multiplă
| align = right
| direction = vertical
| header = 
| image1 = Zkip alibaba1.png
| image2 = Zkip alibaba2.png
| image3 = Zkip alibaba3.png
}}
Există o poveste binecunoscută care prezintă ideile fundamentale ale demonstrațiilor fără divulgare de cunoștințe, publicată pentru prima dată în 1990 de Jean-Jacques Quisquater și alții în lucrarea lor „Cum să explici copiilor tăi protocoalele fără  divulgare de cunoștințe”.<ref>{{Citat carte|prenume=Jean-Jacques|nume=Quisquater|prenume2=Louis C.|nume2=Guillou|prenume3=Thomas A.|nume3=Berson|titlu=Advances in Cryptology — CRYPTO' 89 Proceedings|capitol=How to Explain Zero-Knowledge Protocols to Your Children|volum=435|pagini=628–631|an=1990|url=http://www.cs.wisc.edu/~mkowalcz/628.pdf|doi=10.1007/0-387-34805-0_60|serie=Lecture Notes in Computer Science|isbn=978-0-387-97317-3}}</ref> Cele două părți din povestea cu demonstrații fără divulgare de cunoștințe sunt Denisa ca '''demonstrator''' și Victor, '''verificatorul''' demonstrației.

În această poveste, Denisa a descoperit cuvântul secret folosit pentru a deschide o ușă magică într-o peșteră. Peștera are forma unui inel, cu intrarea pe o parte și ușa magică blocând partea opusă. Victor vrea să știe dacă Denisa cunoaște cuvântul secret; dar Denisa, fiind o persoană foarte privată, nu vrea să-și dezvăluie cunoștințele (cuvântul secret) lui Victor și nici să dezvăluie lumii ceea ce cunoaște.

Ei etichetează cu A și B căile din stânga și din dreapta de la intrare. Mai întâi, Victor așteaptă în afara peșterii când Denisa intră. Denisa o ia fie pe calea A, fie pe calea B; Victor nu are voie să vadă pe ce drum o ia. Apoi, Victor intră în peșteră și strigă numele căii pe care vrea ca Denisa să o folosească pentru a se întoarce, fie A sau B, aleasă la întâmplare. Dacă Denisa cunoaște într-adevăr cuvântul magic, acest lucru este îi este ușor: deschide ușa, dacă este necesar, și se întoarce pe calea dorită.

Totuși, să presupunem că ea nu știa cuvântul. În acest caz, ea s-ar putea întoarce pe calea numită doar dacă Victor ar striga numele aceleiași căi pe care a intrat ea. Deoarece Victor alege A sau B la întâmplare, ea ar avea șanse de 50% să ghicească corect. Dacă cei doi ar repeta acest joc de multe ori, să zicem de 20 de ori la rând, șansa ei de a anticipa cu succes toate cererile lui Victor ar fi redusă la 1 în 2 <sup>20</sup>, sau 9,56 × 10 <sup>−7</sup>.

Astfel, dacă Denisa apare în mod repetat la ieșirea pe care o numește Victor, el poate concluziona că este extrem de probabil ca Denisa să cunoască, de fapt, cuvântul secret.

O observație cu privire la observatorii terți: chiar dacă Victor poartă o cameră ascunsă care înregistrează întreaga tranzacție, singurul lucru pe care camera îl va înregistra este într-un caz Victor strigând „A!” iar Denisa apărând la A sau în celălalt caz Victor strigând "B!" și Denisa apărând la B. O înregistrare de acest tip ar fi trivială pentru oricare doi oameni să o falsifice (cerând doar ca Denisa și Victor să se pună de acord în prealabil asupra secvenței de A și B pe care Victor o va striga). Cu siguranță, o astfel de înregistrare nu va fi niciodată convingătoare pentru nimeni, în afară de participanții inițiali. De fapt, chiar și o persoană care a fost prezentă ca observator la experimentul inițial nu ar fi convins, deoarece Victor și Denisa ar fi putut orchestra întregul „experiment” de la început până la sfârșit.

Dacă însă Victor alege A și B dând cu banul în timp ce se filmează, acest protocol își pierde proprietatea de a nu divulga cunoștințe; filmarea aruncării monedei ar fi probabil convingătoare pentru orice persoană care urmărește înregistrarea mai târziu. Astfel, deși acest lucru nu îi dezvăluie cuvântul secret lui Victor, îi permite lui Victor să convingă pe oricine că Denisa are aceste cunoștințe – contrar dorințelor declarate ale Denisei. Cu toate acestea, criptografia digitală e în general bazată pe „dat cu banul”, bazându-se pe un generator de numere pseudoaleatoare, care este asemănător unei monede cu un model fix de distribuție de cap și pajură, cunoscut doar de proprietarul monedei. Dacă moneda lui Victor s-ar comporta în acest fel, atunci din nou ar fi posibil ca Victor și Denisa să fi falsificat experimentul, așa că utilizarea unui generator de numere pseudoaleatoare nu ar dezvălui lumii cunoștințele Denisei în același mod în care ar fi făcut-o folosind folosirea unei monede.

Observați că Denisa i-ar putea demonstra lui Victor că știe cuvântul magic, fără să i-l dezvăluie, dintr-o singură încercare. Dacă atât Victor, cât și Denisa merg împreună la gura peșterii, Victor o poate vedea pe Denisa intrând prin A și ieșind prin B. Acest lucru ar dovedi cu certitudine că Denisa cunoaște cuvântul magic, fără să-i dezvăluie cuvântul magic lui Victor. Cu toate acestea, o astfel de dovadă ar putea fi observată de un terț sau înregistrată de Victor și o astfel de dovadă ar fi convingătoare pentru oricine. Cu alte cuvinte, Denisa nu ar putea respinge o astfel de dovadă susținând că s-a înțeles cu Victor; prin urmare, nu ar mai deține controlul asupra celor pe care îi alege să își dezvăluie cunoștințele.

=== Două bile și prietenul daltonist ===
Imaginează-ți că prietenul tău „Victor” este [[Daltonism|daltonist]] roșu-verde (în timp ce tu nu ești) și ai două bile: una roșie și una verde, dar în rest identice. Pentru Victor, bilele par complet identice. Victor este sceptic că bilele pot fi de fapt diferențiate. Vrei să''-i demonstrezi lui Victor că bilele sunt de fapt colorate diferit'', dar nimic altceva. Mai ales, nu vrei să dezvălui care bilă este cea roșie și care este cea verde.

Iată sistemul de demonstrație. Îi dai cele două bile lui Victor și le ascunde la spate. Apoi, scoate una dintre bile și o arată. Apoi o ascunde din nou la spate și apoi scoate și arată iar una dintre cele două bile, la întâmplare, cu aceeași probabilitate. Te va întreba: „Am schimbat bila?” Toată această procedură se repetă ori de câte ori este necesar.

Privind culorile bilelor, poți, desigur, să spui cu certitudine dacă le-a schimbat sau nu. Pe de altă parte, dacă bilele ar fi de aceeași culoare și, prin urmare, imposibil de distins, nu ai putea ghici corect cu o probabilitate mai mare de 50%.

Deoarece probabilitatea ca ai fi reușit aleatoriu să identifici fiecare schimbare/ne-schimbare este de 50%, probabilitatea de a fi reușit aleatoriu la '''toate''' schimbările/ne-schimbările se apropie de zero („corectitudine”). Dacă tu și prietenul tău repetați această „demonstrație” de mai multe ori (de exemplu, de 20 de ori), prietenul tău ar trebui să se convingă („completitudine”) că bilele sunt într-adevăr de culoare diferită.

Demonstrația de mai sus este ''fără divulgare de'' ''cunoștințe'' pentru că prietenul tău nu învață niciodată care minge este verde și care este roșie; într-adevăr, el nu obține cunoștințe despre cum să distingă bilele.<ref>{{Citat știre|title=Demonstrate how Zero-Knowledge Proofs work without using maths|url=https://www.linkedin.com/pulse/demonstrate-how-zero-knowledge-proofs-work-without-using-chalkias|prenume=Konstantinos|nume=Chalkias|accessdate=2017-09-13|language=en|journal=CordaCon 2017}}</ref>

=== Unde e Waldo ===
Un exemplu binecunoscut de demonstrație fără divulgare de cunoștințe este exemplul „Unde este Waldo”. În acest exemplu, demonstratorul dorește să-i demonstreze verificatorului că știe unde se află Waldo pe o pagină din cartea ''Unde este Waldo?'', fără a dezvălui verificatorului locația sa.<ref name="Murtagh">{{Citat știre|title=Where's Waldo? How to Mathematically Prove You Found Him without Revealing Where He Is|url=https://www.scientificamerican.com/article/wheres-waldo-how-to-prove-you-found-him-without-revealing-where-he-is/|prenume=Jack|nume=Murtagh|data=July 1, 2023|accessdate=2023-10-02|journal=[[Scientific American]]}}</ref>

Demonstratorul începe prin a lua o placă mare neagră cu o mică gaură în ea, de dimensiunea lui Waldo. Placa are de două ori dimensiunea cărții în ambele direcții, astfel încât verificatorul nu poate vedea unde pe pagină o plasează demonstratorul. Demonstratorul pune apoi placa peste pagină, astfel încât Waldo să fie vizibil prin gaură.<ref name="Murtagh"/>

Verificatorul poate privi acum prin gaură și îl poate vedea pe Waldo, dar nu poate vedea nicio altă parte a paginii. Prin urmare, demonstratorul a dovedit verificatorului că știe unde se află Waldo, fără a dezvălui alte informații despre locația sa.<ref name="Murtagh"/>

Acest exemplu nu este o demonstrație fără divulgare de cunoștințe perfectă, deoarece demonstratorul dezvăluie unele informații despre locația lui Waldo, cum ar fi poziția corpului său. Cu toate acestea, este o ilustrare decentă a conceptului de bază al unei demonstrații fără divulgare de cunoștințe.

=== Sudoku ===
În acest exemplu, Denisa vrea să îi demonstreze lui Victor că știe soluția unei grile de [[Sudoku]]<ref>{{Citat revistă|nume=Gradwohl|nume2=Naor|nume3=Pinkas|nume4=Rothblum|prenume=Ronen|prenume2=Moni|prenume3=Benny|prenume4=Guy N.|dată=2009|titlu=Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles|url=https://www.wisdom.weizmann.ac.il/~naor/PAPERS/sudoku.pdf|journal=Theory Comput. Syst.|volum=44|număr=2|pagini=245 - 268|doi=10.1007/978-3-540-72914-3_16}}</ref>.

Pentru a face acest lucru, după ce a rezolvat grila de Sudoku, Denisa decupează cu grijă grila cu foarfecele. În urma acestui proces, ea obține 81 de pătrate mici de hârtie pe care sunt scrise numerele grilei de Sudoku rezolvate. Ea întoarce apoi bucățile de hârtie cu fața în jos, cu excepția numerelor care erau scrise la început pe grilă (cele prezente înainte de a fi început să rezolve grila). Procedura de demonstrare poate începe.

Victor poate alege orice rând, coloană sau pătrat de 3x3. Denisa ia cele 9 pătrate de hârtie corespunzătoare, le amestecă cu grijă și i le dă lui Victor. Victor poate verifica apoi dacă aceste pătrate conțin numerele de la 1 la 9. Apoi, Denisa pune din nou pătratele mici la locul lor cu fața în jos pe grilă. Victor repetă procedura până când a verificat cele 9 rânduri, 9 coloane și 9 pătrate 3x3 ale grilei Sudoku.

La sfârșitul acestui proces, Victor are dovada că Denisa a rezolvat grila Sudoku, fără însă să fi aflat nimic suplimentar despre grilă.

== Definiție ==
{{Refimprove|section|date=July 2022}}
O demonstrație fără divulgare de cunoștințe a unei afirmații trebuie să satisfacă trei proprietăți:

# '''Completitudine''' (completeness): dacă afirmația este adevărată, un verificator onest (adică unul care urmează protocolul în mod corespunzător) va fi convins de acest fapt de un demonstrator onest.
# '''Corectitudine''' (soundness): dacă afirmația este falsă, niciun demonstrator trișor nu poate convinge un verificator onest că afirmația este adevărată, decât cu probabilitate redusă.
# '''Nici o informație suplimentară''' (zero-knowledge): dacă afirmația este adevărată, niciun verificator nu învață altceva decât faptul că afirmația este adevărată. Cu alte cuvinte, doar cunoașterea afirmației (nu a secretului) este suficientă pentru a imagina un scenariu care arată că cel care dovedește cunoaște secretul. Acest lucru este formalizat arătând că fiecare verificator are un ''simulator'' care, pornind doar de la afirmația care trebuie demonstrată (și fără acces la demonstrator), poate produce o transcriere care „pare” o interacțiune între un demonstrator onest și verificatorul în cauză.

Primele două dintre aceste proprietăți caracterizează noțiunea mai generală a sistemelor de demonstrare interactive. Al treilea este ceea ce face ca demonstrația să fie fără divulgare de cunoștințe.<ref>{{Citat revistă|nume=Feige|nume2=Fiat|nume3=Shamir|prenume=Uriel|prenume2=Amos|prenume3=Adi|dată=1988-06-01|titlu=Zero-knowledge proofs of identity|journal=Journal of Cryptology|volum=1|număr=2|pagini=77–94|language=en|issn=1432-1378|doi=10.1007/BF02351717}}</ref>

Demonstrațiile fără divulgare de cunoștințe nu sunt demonstrații în sensul matematic al termenului, deoarece există o mică probabilitate, ''eroarea de corectitudine'', ca un demonstrator trișor să poată convinge verificatorul de o afirmație falsă. Cu alte cuvinte, demonstrațiile fără divulgare de cunoștințe sunt „demonstrații” probabiliste mai degrabă decât demonstrații deterministe. Cu toate acestea, există tehnici pentru a reduce eroarea de corectitudine la valori neglijabil de mici (de exemplu, ghicirea corectă a unei sute sau mii de decizii binare are o eroare de corectitudine de <math>1 / 2 ^ {100}</math> sau <math>1 / 2 ^ {1000}</math>, respectiv. Pe măsură ce numărul de biți crește, eroarea de corectitudine scade spre zero).

O definiție formală a proprietății de nedivulgare a cunoștințelor trebuie să folosească un model de calcul, cel mai comun fiind cel al unei [[Mașină Turing|mașini Turing]]. Fie {{Mvar|D}}, {{Mvar|V}} și {{Mvar|S}} mașini Turing. Un sistem de demonstrare interactiv cu <math>(D, V) </math> pentru un limbaj {{Mvar|L}} este fără divulgare de cunoștințe dacă pentru orice verificator probabilistic de timp polinomial (PPT). <math>\hat{V}</math> există un simulator PPT {{Mvar|S}} astfel încât:

: <math>\forall x \in L, z \in \{0, 1\}^{*}, \operatorname{Transcriere}_{\hat V} \left[D(x) \leftrightarrow \hat V(x, z)\right] = S(x, z)</math>

Unde <math> \operatorname{Transcriere}_{\hat V} \left[D(x) \leftrightarrow \hat V(x, z)\right]</math> este o înregistrare a interacțiunilor dintre <math>D(x)</math> și <math>\hat V(x, z)</math>. Demonstratorul {{Mvar|D}} este modelat ca având putere de calcul nelimitată (în practică, {{Mvar|D}} este de obicei o mașină Turing probabilistică ). Intuitiv, definiția afirmă că un sistem de dovezi interactiv <math>(D, V) </math> este fără divulgare de cunoștințe dacă pentru orice verificator <math>\hat{V}</math> există un simulator {{Mvar|S}} eficient (în funcție de <math>\hat V</math> ) care poate reproduce conversația dintre {{Mvar|D}} și <math>\hat{V}</math> pe orice intrare dată. Șirul auxiliar {{Mvar|z}} din definiție joacă rolul de „cunoștințe anterioare” (inclusiv monedele aleatorii ale <math>\hat V</math> ). Definiția presupune că <math>\hat{V}</math> nu poate folosi niciun șir de cunoștințe anterioare {{Mvar|z}} pentru a extrage informații din conversația sa cu {{Mvar|D}}, deoarece dacă simulatorului {{Mvar|S}} i se oferă și această cunoaștere anterioară, atunci acesta poate reproduce conversația dintre <math>\hat{V}</math> și {{Mvar|D}} la fel ca înainte.

Definiția dată este cea a noțiunii perfecte de nedivulgare de cunoștințe. Noțiunea computațională de nedivulgare de cunoștințe este obținută prin relaxarea condiției de mai sus, cerând doar ca înregistrările interacțiunilor dintre verificatorului <math>\hat{V}</math> și simulatorul nu se pot distinge din punct de vedere computațional, folosind șirul auxiliar.


== Exemple practice ==

=== Logaritmul discret al unei valori date ===
De exemplu, dată fiind o valoare <math>y</math>, un număr [[Număr prim|prim mare]] <math>p</math> și un generator <math>g</math>, Denisa vrea să demonstreze că știe o valoare <math>x</math> astfel încât <math>g^x \bmod{p} = y</math>, fără a dezvălui <math>x</math>. Într-adevăr, faptul că Denisa ar cunoaște numărul <math>x</math> ar putea fi folosită ca dovadă a identității, în sensul că Denisa ar putea avea astfel de cunoștințe pentru că a ales o valoare aleatorie <math>x</math> pe care nu a dezvăluit-o nimănui, a calculat <math>y = g^x \bmod{p}</math> și a distribuit valoarea <math>y</math> tuturor verificatorilor potențiali, astfel încât, ulterior, demonstrarea faptului că știe valoarea lui <math>x</math> să fie echivalent cu a-și demonstra identitatea ca Denisa.

Protocolul decurge după cum urmează: în fiecare rundă, Denisa generează un număr aleatoriu <math>r</math>, calculează <math>C = g^r \bmod{p}</math> și îi dezvăluie asta lui Victor. După primirea lui <math>C</math>, Victor emite aleatoriu una dintre următoarele două solicitări: fie cere ca Denisa să dezvăluie valoarea <math>r</math>, sau valoarea expresiei <math>(x + r) \bmod{(p - 1)}</math>.

Victor poate verifica oricare dintre răspunsuri; dacă a cerut <math>r</math>, apoi poate calcula valoarea expresiei <math>g^r \bmod{p}</math> și verifica dacă aceasta este egală cu <math>C</math>. Dacă a cerut <math>(x + r) \bmod{(p - 1)}</math>, poate verifica dacă <math>C</math> este în concordanță cu aceasta, calculând <math>g^{(x + r) \bmod{(p - 1)}} \bmod{p}</math> și verificând dacă se valoarea sa este egală cu <math>(C \cdot y) \bmod{p}</math>. Dacă Denisa știe într-adevăr valoarea <math>x</math>, ea poate răspunde la oricare dintre posibilele provocări ale lui Victor.

Dacă Denisa știa sau ar putea ghici ce provocare va lansa Victor, atunci ar putea să-l înșele cu ușurință și să-l convingă pe Victor că știe <math>x</math> când de fapt nu îl știe: dacă știe că Victor va cere <math>r</math>, apoi procedează normal: ea alege <math>r</math>, calculează <math>C = g^r \bmod{p}</math> și dezvăluie <math>C</math> lui Victor; ea va putea răspunde provocării lui Victor. Pe de altă parte, dacă știe că Victor va cere <math>(x + r) \bmod{(p - 1)}</math>, apoi alege o valoare aleatorie <math>r'</math>, calculează <math>C' = g^{r'} \cdot \left(g^x\right)^{-1} \bmod{p}</math>, și dezvăluie <math>C'</math> lui Victor ca valoarea <math>C</math> la care acesta se aștepta. Când Victor o provoacă să dezvăluie <math>(x + r) \bmod{(p - 1)}</math>, ea dezvăluie <math>r'</math>, pentru care Victor va verifica consistența, deoarece va calcula la rândul său <math>g^{r'} \bmod{p}</math>, care va fi egală cu <math>C' \cdot y</math>, deoarece Denisa a înmulțit cu inversul multiplicativ modular al lui <math>y</math>.

Totuși, dacă în oricare dintre scenariile de mai sus, Victor lansează o altă provocare decât cea pe care Denisa o aștepta și pentru care a produs rezultatul, atunci ea nu va putea răspunde provocării sub ipoteza infezabilității rezolvării problemei logaritmului discret pentru acest grup. Dacă ea a ales <math>r</math> și a dezvăluit <math>C = g^r \bmod{p}</math>, atunci ea nu va putea produce un valoare validă <math>(x + r) \bmod{(p - 1)}</math> care ar trece de verificarea lui Victor, în condițiile în care ea nu știe valoarea lui <math>x</math>. Și dacă a ales o valoare <math>r'</math> pe post de <math>(x + r) \bmod{(p - 1)}</math>, ca mai sus, atunci ea ar trebui să răspundă cu logaritmul discret al valorii pe care a dezvăluit-o – dar Denisa nu cunoaște acest logaritm discret, deoarece valoarea C pe care a dezvăluit-o a fost obținută prin aritmetică cu valori cunoscute și nu prin calculul unei puteri cu un exponent cunoscut.

Astfel, un demonstrator trișor are o probabilitate de 0,5 de a trișa cu succes într-o rundă. Prin executarea unui număr suficient de mare de runde, probabilitatea ca un demonstrator trișor să reușească poate fi redusă în mod arbitrar.

Pentru a arăta că demonstrația interactivă de mai sus nu divulgă alte cunoștințe în afară de faptul că Denisa cunoaște valoare lui <math>x</math>, se pot folosi argumente similare cu cele folosite în demonstrația de mai sus a completitudinii și corectitudinii. Mai exact, un simulator, să zicem Simon, care nu cunoaște valoarea lui <math>x</math>, poate simula schimbul de mesaje dintre Denisa și Victor folosind următoarea procedură. În primul rând, Simon dă cu banul folosind o monedă corectă. Dacă rezultatul este „cap”, el alege o valoare aleatorie <math>r</math>, calculează <math>C = g^{r} \bmod{p}</math>, și dezvăluie <math>C</math> ca mesaj de la Denisa către Victor. Apoi Simon trimite și un mesaj „cerere valoarea lui <math>r</math> " ca și cum ar fi trimis de la Victor către Denisa și emite imediat valoarea lui <math>r</math> ca mesaj de la Denisa la Victor. O rundă este completă. Pe de altă parte, dacă rezultatul aruncării monedei este „pajură”, Simon alege un număr aleatoriu <math>r'</math>, calculează <math>C' = g^{r'} \cdot \left(y\right)^{-1} \bmod{p}</math>, și dezvăluie <math>C'</math> ca mesaj de la Denisa către Victor. Apoi Simon dă „cerere valoarea lui <math>(x + r) \bmod{(p - 1)}</math>" ca mesaj de la Victor către Denisa. În cele din urmă, Simon emite valoarea lui <math>r'</math> ca răspunsul al Denisei către Victor. O rundă este completă. Folosind argumentele anterioare din demonstrațiile completitudinii și corectitudinii, comunicarea interactivă simulată de Simon nu se distinge de adevărata corespondență dintre Denisa și Victor. Proprietatea de nedivulgare de cunoștințe este astfel garantată.

==== Rezumat ====
Denisa dovedește că știe valoarea lui x (de exemplu parola ei).

# Denisa și Victor cad de acord asupra unui număr prim <math>p</math> și a un generator <math>g</math> al grupului multiplicativ al lui <math>\mathbb{Z}_{p}</math>.
# Denisa calculează valoarea expresiei <math>y = g^x \bmod{p}</math> și i-o trimite lui Victor.
# Următorii doi pași se repetă de un număr (mare) de ori.
## Denisa alege în mod repetat o valoare aleatorie <math>r\in U[0, p-2]</math> și calculează <math>C = g^r \bmod{p}</math>. Ea îi trimite lui Victor valoarea <math>C </math>.
## Victor îi cere Denisei să calculeze și să trimită înapoi valoarea <math>(x + r) \bmod{(p-1)}</math> sau valoarea <math> r </math>. În primul caz Victor verifică <math>(C \cdot y) \bmod{p}\equiv g^{(x + r) \bmod{(p - 1)}} \bmod{p} </math>. În al doilea caz el verifică <math> C \equiv g^{r} \bmod{p}</math>.

Valoarea <math>(x + r) \bmod (p-1)</math> poate fi văzută ca valoarea criptată a lui <math>x \bmod (p-1)</math>. Dacă <math>r</math> este cu adevărat aleatorie, distribuită egal între zero și <math>(p-2)</math>, acest lucru nu scurge nicio informație despre <math>x</math>.

=== Ciclul hamiltonian pentru un grafic mare ===
Următoarea schemă se datorează lui [[Manuel Blum]].<ref name="blum86">{{Citat revistă|nume=Blum|prenume=Manuel|an=1986|titlu=How to Prove a Theorem So No One Else Can Claim It|urlarhivă=https://web.archive.org/web/20230103032937/http://euler.nmt.edu/~brian/students/pope.pdf|url=http://euler.nmt.edu/~brian/students/pope.pdf|journal=ICM Proceedings|pagini=1444–1451|archive-date=January 3, 2023}}</ref>

În acest scenariu, Denisa cunoaște un [[Drum hamiltonian|ciclu hamiltonian]] pentru un [[graf]] mare {{Math|{{var|G}}}}. Victor cunoaște {{Math|{{var|G}}}} dar nu și ciclul (de exemplu, Denisa a generat {{Math|{{var|G}}}} și i l-a dezvăluit lui Victor). Se crede că găsirea unui ciclu hamiltonian pentru un graf mare este nefezabilă din punct de vedere computațional, deoarece problema de decizie corespunzătoare este cunoscută ca fiind [[NP-completitudine|NP-completă]]. Denisa va dovedi că știe ciclul fără să-l dezvăluie pur și simplu (poate că Victor este interesat să-l cumpere, dar dorește mai întâi verificarea, sau poate că Denisa este singura care cunoaște aceste informații și își dovedește astfel identitatea lui Victor).

Pentru a arăta că Denisa cunoaște acest ciclu hamiltonian, ea și Victor joacă mai multe runde ale unui joc:

* La începutul fiecărei runde, Denisa creează {{Math|{{var|H}}}}, un graf izomorf cu {{Math|{{var|G}}}} (adică {{Math|{{var|H}}}} este la fel ca {{Math|{{var|G}}}}, cu excepția faptului că toate vârfurile au nume diferite). Deoarece este trivial să transferăm un ciclu hamiltonian între grafuri izomorfe dat fiind un izomorfism cunoscut, dacă Denisa cunoaște un ciclu hamiltonian pentru {{Math|{{var|G}}}}, trebuie să cunoască și unul pentru {{Math|{{var|H}}}}.
* Denisa își ia un angajament față de alegerea {{Math|{{var|H}}}}. Ea ar putea face acest lucru folosind o schemă de angajament criptografic. Alternativ, ea ar putea numerota vârfurile lui {{Math|{{var|H}}}}. Apoi, pentru fiecare muchie a grafului {{Math|{{var|H}}}}, pe o bucată mică de hârtie, ea notează cele două vârfuri unite de muchie. Apoi pune toate aceste bucăți de hârtie cu fața în jos pe o masă. Scopul acestui angajament este ca Denisa să nu fie capabilă să schimbe {{Math|{{var|H}}}}, în timp ce, în același timp, Victor nu are informații despre {{Math|{{var|H}}}}.
* Victor alege apoi la întâmplare una dintre cele două întrebări pe care să le pună Denisei. El îi poate cere fie să arate izomorfismul dintre {{Math|{{var|H }}}} și {{Math|{{var|G}}}}, fie îi poate cere să arate un ciclu hamiltonian în {{Math|{{var|H}}}}.
* Dacă Denisei i se cere să arate că cele două grafuri sunt izomorfe, ea descoperă mai întâi întreg graful {{Math|{{var|H}}}} (de exemplu, răsturnând toate bucățile de hârtie pe care le-a pus pe masă) și apoi furnizează translațiile vârfurilor care mapează {{Math|{{var|G}}}} la {{Math|{{var|H}}}}. Victor poate verifica că acestea sunt într-adevăr izomorfe.
* Dacă Denisei i se cere să demonstreze că știe un ciclu hamiltonian în {{Math|{{var|H}}}}, ea își translatează ciclul hamiltonian din {{Math|{{var|G}}}} în {{Math|{{var|H}}}} și descoperă doar muchiile ciclului hamiltonian. Adică, Denisa întoarce doar exact <math>|V(G)|</math> bucăți de hârtie care corespund muchilor ciclului hamiltonian, lăsând restul cu fața în jos. Acest lucru este suficient pentru ca Victor să verifice că {{Math|{{var|H}}}} conține într-adevăr un ciclu hamiltonian.

Este important ca angajamentul față de graf să fie astfel încât Victor să poată verifica, în al doilea caz, că ciclul este într-adevăr format din muchii din {{Math|{{var|H}}}}. Acest lucru se poate face, de exemplu, luând angajamentul față de fiecare muchie (sau lipsa acesteia) separat.

==== Completitudine ====
Dacă Denisa cunoaște un ciclu hamiltonian în {{Math|{{var|G}}}}, ea poate satisface cu ușurință cererea lui Victor fie pentru izomorfismul de grafuri care produce {{Math|{{var|H}}}} din {{Math|{{var|G}}}} (la care s-a angajat în primul pas), fie un ciclu hamiltonian în {{Math|{{var|H}}}} (pe care îl poate construi aplicând izomorfismul la ciclul din {{Math|{{var|G}}}} ).

==== '''Nici o informație suplimentară''' (zero-knowledge) ====
Răspunsurile Denisei nu dezvăluie ciclul hamiltonian din graful original {{Math|{{var|G}}}}. În fiecare rundă, Victor va învăța doar un izomorfism de la un graf {{Math|{{var|H}}}} la {{Math|{{var|G}}}} sau un ciclu hamiltonian în {{Math|{{var|H}}}}. Ar avea nevoie de ambele răspunsuri pentru un singur {{Math|{{var|H}}}} pentru a descoperi ciclul în {{Math|{{var|G}}}}, așa că informațiile rămân necunoscute atâta timp cât Denisa poate genera un {{Math|{{var|H}}}} distinct în fiecare rundă. Dacă Denisa nu știe despre un ciclu hamiltonian în {{Math|{{var|G}}}}, dar știa cumva dinainte ce ar cere Victor să vadă fiecare rundă, atunci ar putea trișa. De exemplu, dacă Denisa știa dinainte că Victor va cere să vadă ciclul hamiltonian în {{Math|{{var|H}}}}, atunci ar putea genera un ciclu hamiltonian pentru un grafic fără legătură. În mod similar, dacă Denisa știa dinainte că Victor va cere să vadă izomorfismul, atunci ea ar putea pur și simplu să genereze un graf izomorf {{Math|{{var|H}}}} (în care nici ea nu cunoaște un ciclu hamiltonian). Victor ar putea simula protocolul singur (fără Denisa) pentru că știe ce va cere să vadă. Prin urmare, Victor nu obține informații despre ciclul hamiltonian în {{Math|{{var|G}}}} din informațiile dezvăluite în fiecare rundă.

==== Corectitudine ====
Dacă Denisa nu cunoaște informațiile, ea poate ghici ce întrebare va pune Victor și poate genera fie un graf izomorf cu {{Math|{{var|G}}}}, fie un ciclu hamiltonian pentru un graf neînrudit, dar, deoarece nu cunoaște un ciclu hamiltonian pentru {{Math|{{var|G}}}}, nu le poate face pe amândouă. Cu această presupunere, șansa ei de a-l păcăli pe Victor este {{Math|2<sup>−{{var|n}}</sup>}}, unde {{Math|{{var|n}}}} este numărul de runde. Este complet nerealist că Denisa ar putea să îl înșele pe Victor în acest fel dat fiind un număr rezonabil de runde.

== Variante de nedivulgare de cunoștințe ==
Diferite variante a ideii de nedivulgare de cunoștințe pot fi definite prin formalizarea conceptului intuitiv a ceea ce se înțelege prin rezultatul produs de simulator „care nu poate fi distins de” execuția reală a protocolului de demonstrație, în următoarele moduri:

* Vorbim de ''nedivulgare de cunoștințe'' ''perfectă'' dacă distribuțiile produse de simulator și protocolul de demonstrare sunt exact la fel. Acesta este, de exemplu, cazul în primul exemplu de mai sus.
* ''Nedivulgare de cunoștințe'' ''din punct de vedere statistic''<ref>{{Citat revistă|nume=Sahai|nume2=Vadhan|prenume=Amit|prenume2=Salil|dată=1 March 2003|titlu=A complete problem for statistical zero knowledge|urlarhivă=https://web.archive.org/web/20150625193124/http://dash.harvard.edu/bitstream/handle/1/4728406/Vadhan_StatZeroKnow.pdf?sequence=2|url=http://dash.harvard.edu/bitstream/handle/1/4728406/Vadhan_StatZeroKnow.pdf?sequence=2|journal=Journal of the ACM|volum=50|număr=2|pagini=196–249|doi=10.1145/636865.636868|archive-date=2015-06-25}}</ref> înseamnă că distribuțiile nu sunt neapărat exact aceleași, dar sunt apropiate statistic, ceea ce înseamnă că diferența lor statistică este o funcție neglijabilă.
* Vorbim de ''nedivulgare de cunoștințe din punct de vedere'' ''computațional'' dacă niciun [[algoritm]] eficient nu poate distinge cele două distribuții.

== Aplicații ==

=== Sisteme de autentificare ===
Cercetarea în domeniul demonstrațiilor fără divulgare de cunoștințe a fost motivată de sistemele [[Autentificare|de autentificare]] în care o parte dorește să-și demonstreze identitatea unei alte părți prin intermediul unor informații secrete (cum ar fi o parolă), dar nu dorește ca a doua parte să învețe nimic despre acest secret. Aceasta se numește „dovadă de cunoaștere fără divulgare de cunoștințe”. Cu toate acestea, o parolă este de obicei prea mică sau insuficient aleatorie pentru a fi utilizată în multe scheme pentru dovezi de cunoaștere fără divulgare de cunoștințe.

=== Dezarmare nucleară ===
În 2016, Princeton Plasma Physics Laboratory și [[Universitatea Princeton|Princeton University]] au demonstrat o tehnică care poate avea aplicabilitate la viitoarele discuții privind dezarmarea nucleară. Ar permite inspectorilor să confirme dacă un obiect este într-adevăr o armă nucleară fără a înregistra, împărtăși sau dezvălui funcționarea internă care ar putea fi secretă.<ref>{{Citat web|url=http://www.pppl.gov/news/2016/09/pppl-and-princeton-demonstrate-novel-technique-may-have-applicability-future-nuclear|titlu=PPPL and Princeton demonstrate novel technique that may have applicability to future nuclear disarmament talks - Princeton Plasma Physics Lab|archiveurl=https://web.archive.org/web/20170703142802/https://www.pppl.gov/news/2016/09/pppl-and-princeton-demonstrate-novel-technique-may-have-applicability-future-nuclear|lucrare=www.pppl.gov|archivedate=2017-07-03}}</ref>

=== Blockchain-uri ===
Demonstrațiile fără divulgare de cunoștințe au fost aplicate în protocoalele Zerocoin și Zerocash, care au culminat cu nașterea [[Zcoin]]<ref name="Hellwig 2020">{{Citat carte|nume=Hellwig|prenume=Daniel|nume2=Karlic|prenume2=Goran|nume3=Huchzermeier|prenume3=Arnd|titlu=Build Your Own Blockchain|serie=Management for Professionals|dată=3 May 2020|editură=SpringerLink|isbn=9783030401429|pagină=112|url-capitol=https://link.springer.com/chapter/10.1007/978-3-030-40142-9_5|data-accesării=3 December 2020|capitol=Privacy and Anonymity|doi=10.1007/978-3-030-40142-9_5}}</ref> (care și-a schimbat numele în [[Zcoin|Firo]] în 2020, în urma unui proces de rebranding)<ref>{{Citat web|url=https://www.crowdfundinsider.com/2020/10/168504-zcoin-announces-rebranding-to-new-name-ticker-firo/|nume=Hurst|titlu=Zcoin Announces Rebranding to New Name & Ticker "Firo"|publisher=Crowdfund Insider|date=28 October 2020|accessdate=4 November 2020|archiveurl=https://web.archive.org/web/20201101141745/https://www.crowdfundinsider.com/2020/10/168504-zcoin-announces-rebranding-to-new-name-ticker-firo/|first1=Samantha|archivedate=1 November 2020}}</ref> și criptomonedele [[Zcash]] în 2016.

În 2018, au fost introduse Bulletproofs. Bulletproofs reprezintă o îmbunătățire față de demonstrațiile ne-interactive fără divulgare de cunoștințe, în care nu este necesară încrederea într-o configurare inițială.<ref name="Bulletproofs">{{Citat carte|nume=Bünz|prenume=B|nume2=Bootle|prenume2=D|nume3=Boneh|prenume3=A|titlu=2018 IEEE Symposium on Security and Privacy (SP)|capitol=Bulletproofs: Short Proofs for Confidential Transactions and More|dată=2018|pagini=315–334|doi=10.1109/SP.2018.00020|locul-publicării=San Francisco, California|isbn=978-1-5386-4353-2}}</ref> Ulterior aceste idei au fost implementate în protocolul Mimblewimble (pe care se bazează criptomonedele Grin și Beam) și criptomoneda Monero.<ref>{{Citat web|url=https://tlu.tarilabs.com/cryptography/bulletproofs-and-mimblewimble/MainReport.html#current-and-past-efforts|nume=Odendaal|titlu=Bulletproofs and Mimblewimble|publisher=Tari Labs University|accessdate=3 December 2020|archiveurl=https://web.archive.org/web/20200929160834/https://tlu.tarilabs.com/cryptography/bulletproofs-and-mimblewimble/MainReport.html|first1=Hansie|last2=Sharrock|last3=Heerden|first2=Cayle|first3=SW|archivedate=29 September 2020}}</ref>

== Istorie ==
Demonstrațiile fără divulgare de cunoștințe au fost concepute pentru prima dată în 1985 de Shafi Goldwasser, Silvio Micali și Charles Rackoff în lucrarea lor „The Knowledge Complexity of Interactive Proof-Systems”.<ref name="knowledgecomplexity">{{Citation|last=Goldwasser|first=S.|title=The knowledge complexity of interactive proof systems|url=http://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf|volume=18|issue=1|pages=186–208|year=1989|periodical=SIAM Journal on Computing|doi=10.1137/0218012|issn=1095-7111|last2=Micali|first2=S.|last3=Rackoff|first3=C.}}</ref> Această lucrare a introdus ierarhia '''IP''' a sistemelor interactive de deducție și conceptul de ''complexitate a cunoștințelor'', o măsură a cantității de cunoștințe despre o demonstrație care se scurg de la demonstrator către verificator. Ei au dat, de asemenea, prima demonstrație fără divulgare de cunoștințe pentru o problemă concretă, aceea de a decide non-reziduurile pătratice modulo {{Var|m}}. Împreună cu o lucrare a lui László Babai și Shlomo Moran, această lucrare emblematică a inventat sisteme interactive de deducție, pentru care toți cei cinci autori au câștigat primul premiu Gödel în 1993.

O altă variantă a demonstrațiilor fără divulgare de cunoștințe sunt demonstrațiile non-interactive fără divulgare de cunoștințe. Blum, Feldman și Micali au arătat că un șir aleatoriu comun împărțit între demonstrator și verificator este suficient pentru a obține nedivulgare de cunoștințe din punct de vedere computațional fără a necesita interacțiune.<ref name="noninteractive"/><ref name="noninteractive2"/>

== Protocoale de demonstrare fără divulgare de cunoștințe ==
Cele mai populare protocoale interactive sau non-interactive de demonstrare fără divulgare de cunoștințe (de exemplu, zk-SNARK) pot fi clasificate în linii mari în următoarele patru categorii: argumente de cunoaștere succinte non-interactive (SNARK), argumente de cunoaștere transparente scalabile (STARK), Delegare polinomială verificabilă (VPD) și argumente succinte non-interactive (SNARG). O listă de protocoale și biblioteci de demonstrare fără divulgare de cunoștințe este furnizată mai jos, împreună cu comparații bazate pe '''transparență''', '''universalitate''', '''securitate post-cuantică plauzibilă''' și '''paradigmă de programare'''.<ref name="mouris21">{{Citat revistă|nume=Mouris|nume2=Tsoutsos|prenume=Dimitris|prenume2=Nektarios Georgios|dată=2021|titlu=Zilch: A Framework for Deploying Transparent Zero-Knowledge Proofs|url=https://ieeexplore.ieee.org/document/9410618|journal=IEEE Transactions on Information Forensics and Security|volum=16|pagini=3269–3284|issn=1556-6021|doi=10.1109/TIFS.2021.3074869}}</ref> Un protocol transparent este unul care nu necesită nicio configurare inițială de încredere și folosește surse publice pentru generarea numerelor aleatoare. Un protocol universal este unul care nu necesită o configurare de încredere separată pentru fiecare circuit. În cele din urmă, un protocol post-cuantic plauzibil este unul care nu este susceptibil la atacuri cunoscute care implică algoritmi cuantici.

{| class="wikitable"
|+Sisteme de demonstrare fără divulgare de cunoștințe
!ZKP System
!Publication year
!Protocol
!Transparent
!Universal
!Plauzibil sigur post-quantum
!Paradigma de programare
|-
|Pinocchio<ref>{{cite book|last1=Parno|first1=B.|last2=Howell|first2=J.|last3=Gentry|first3=C.|last4=Raykova|first4=M.|title=2013 IEEE Symposium on Security and Privacy|chapter=Pinocchio: Nearly Practical Verifiable Computation|date=May 2013|pages=238–252|doi=10.1109/SP.2013.47|isbn=978-0-7695-4977-4|s2cid=1155080}}</ref>
|2013
|zk-SNARK
|Nu
|Nu
|Nu
|Procedural
|-
|Geppetto<ref>{{cite book|last1=Costello|first1=Craig|last2=Fournet|first2=Cedric|last3=Howell|first3=Jon|last4=Kohlweiss|first4=Markulf|last5=Kreuter|first5=Benjamin|last6=Naehrig|first6=Michael|last7=Parno|first7=Bryan|last8=Zahur|first8=Samee|title=2015 IEEE Symposium on Security and Privacy|chapter=Geppetto: Versatile Verifiable Computation|date=May 2015|pages=253–270|doi=10.1109/SP.2015.23|hdl=20.500.11820/37920e55-65aa-4a42-b678-ef5902a5dd45|isbn=978-1-4673-6949-7|s2cid=3343426|chapter-url=https://www.research.ed.ac.uk/en/publications/37920e55-65aa-4a42-b678-ef5902a5dd45|hdl-access=free}}</ref>
|2015
|zk-SNARK
|Nu
|Nu
|Nu
|Procedural
|-
|TinyRAM<ref>{{cite book|last1=Ben-Sasson|first1=Eli|last2=Chiesa|first2=Alessandro|last3=Genkin|first3=Daniel|last4=Tromer|first4=Eran|last5=Virza|first5=Madars|title=Advances in Cryptology – CRYPTO 2013|chapter=SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge|series=Lecture Notes in Computer Science|date=2013|volume=8043|pages=90–108|doi=10.1007/978-3-642-40084-1_6|hdl=1721.1/87953|isbn=978-3-642-40083-4|hdl-access=free}}</ref>
|2013
|zk-SNARK
|Nu
|Nu
|Nu
|Procedural
|-
|Buffet<ref>{{cite journal|last1=Wahby|last2=Setty|last3=Ren|last4=Blumberg|last5=Walfish|first1=Riad S.|first2=Srinath|first3=Zuocheng|first4=Andrew J.|first5=Michael|date=2015|title=Efficient RAM and Control Flow in Verifiable Outsourced Computation|journal=Proceedings 2015 Network and Distributed System Security Symposium|isbn=978-1-891562-38-9|doi=10.14722/ndss.2015.23097}}</ref>
|2015
|zk-SNARK
|Nu
|Nu
|Nu
|Procedural
|-
|ZoKrates<ref>{{cite book|last1=Eberhardt|first1=Jacob|last2=Tai|first2=Stefan|title=2018 IEEE International Conference on Internet of Things (IThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData)|chapter=ZoKrates - Scalable Privacy-Preserving Off-Chain Computations|date=July 2018|pages=1084–1091|doi=10.1109/Cybermatics_2018.2018.00199|isbn=978-1-5386-7975-3|s2cid=49473237}}</ref>
|2018
|zk-SNARK
|Nu
|Nu
|Nu
|Procedural
|-
|xJsnark<ref>{{cite book|last1=Kosba|first1=Ahmed|last2=Papamanthou|first2=Charalampos|last3=Shi|first3=Elaine|title=2018 IEEE Symposium on Security and Privacy (SP)|chapter=XJsnark: A Framework for Efficient Verifiable Computation|date=May 2018|pages=944–961|doi=10.1109/SP.2018.00018|isbn=978-1-5386-4353-2|doi-access=free}}</ref>
|2018
|zk-SNARK
|Nu
|Nu
|Nu
|Procedural
|-
|vRAM<ref>{{cite book|last1=Zhang|first1=Yupeng|last2=Genkin|first2=Daniel|last3=Katz|first3=Jonathan|last4=Papadopoulos|first4=Dimitrios|last5=Papamanthou|first5=Charalampos|title=2018 IEEE Symposium on Security and Privacy (SP)|chapter=VRAM: Faster Verifiable RAM with Program-Independent Preprocessing|date=May 2018|pages=908–925|doi=10.1109/SP.2018.00013|isbn=978-1-5386-4353-2|doi-access=free}}</ref>
|2018
|zk-SNARG
|Nu
|Da
|Nu
|Limbaj de asamblare
|-
|vnTinyRAM<ref>{{cite journal|last1=Ben-Sasson|last2=Chiesa|last3=Tromer|last4=Virza|first1=Eli|first2=Alessandro|first3=Eran|first4=Madars|date=20 August 2014|title=Succinct non-interactive zero knowledge for a von Neumann architecture|url=https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/ben-sasson|journal=Proceedings of the 23rd USENIX Conference on Security Symposium|pages=781–796|publisher=USENIX Association|isbn=9781931971157}}</ref>
|2014
|zk-SNARK
|Nu
|Da
|Nu
|Procedural
|-
|MIRAGE<ref>{{cite journal|last1=Kosba|last2=Papadopoulos|last3=Papamanthou|last4=Song|first1=Ahmed|first2=Dimitrios|first3=Charalampos|first4=Dawn|date=2020|title=MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs|url=https://eprint.iacr.org/2020/278|journal=Cryptology ePrint Archive}}</ref>
|2020
|zk-SNARK
|Nu
|Da
|Nu
|Circuite aritmetice
|-
|Sonic<ref>{{cite book|last1=Maller|first1=Mary|last2=Bowe|first2=Sean|last3=Kohlweiss|first3=Markulf|last4=Meiklejohn|first4=Sarah|title=Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security|chapter=Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings|date=6 November 2019|pages=2111–2128|doi=10.1145/3319535.3339817|chapter-url=https://doi.org/10.1145/3319535.3339817|publisher=Association for Computing Machinery|hdl=20.500.11820/739b94f1-54f0-4ec3-9644-3c95eea1e8f5|isbn=9781450367479|s2cid=242772913|url=https://www.research.ed.ac.uk/en/publications/739b94f1-54f0-4ec3-9644-3c95eea1e8f5|hdl-access=free}}</ref>
|2019
|zk-SNARK
|Nu
|Da
|Nu
|Circuite aritmetice
|-
|Marlin<ref>{{cite book|last1=Chiesa|first1=Alessandro|last2=Hu|first2=Yuncong|last3=Maller|first3=Mary|last4=Mishra|first4=Pratyush|last5=Vesely|first5=Noah|last6=Ward|first6=Nicholas|title=Advances in Cryptology – EUROCRYPT 2020|chapter=Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS|series=Lecture Notes in Computer Science|date=2020|volume=12105|pages=738–768|doi=10.1007/978-3-030-45721-1_26|chapter-url=https://link.springer.com/chapter/10.1007/978-3-030-45721-1_26|publisher=Springer International Publishing|isbn=978-3-030-45720-4|s2cid=204772154|language=en}}</ref>
|2020
|zk-SNARK
|Nu
|Da
|Nu
|Circuite aritmetice
|-
|PLONK<ref>{{cite journal|last1=Gabizon|last2=Williamson|last3=Ciobotaru|first1=Ariel|first2=Zachary J.|first3=Oana|date=2019|title=PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge|url=https://eprint.iacr.org/2019/953|journal=Cryptology ePrint Archive}}</ref>
|2019
|zk-SNARK
|Nu
|Da
|Nu
|Circuite aritmetice
|-
|SuperSonic<ref>{{cite book|last1=Bünz|first1=Benedikt|last2=Fisch|first2=Ben|last3=Szepieniec|first3=Alan|title=Advances in Cryptology – EUROCRYPT 2020|chapter=Transparent SNARKs from DARK Compilers|series=Lecture Notes in Computer Science|date=2020|volume=12105|pages=677–706|doi=10.1007/978-3-030-45721-1_24|chapter-url=https://link.springer.com/chapter/10.1007/978-3-030-45721-1_24|publisher=Springer International Publishing|isbn=978-3-030-45720-4|s2cid=204892714|language=en}}</ref>
|2020
|zk-SNARK
|Da
|Da
|Nu
|Circuite aritmetice
|-
|Bulletproofs<ref name="Bulletproofs2">{{cite book|last1=Bünz|first1=B|last2=Bootle|first2=D|last3=Boneh|first3=A|title=2018 IEEE Symposium on Security and Privacy (SP)|chapter=Bulletproofs: Short Proofs for Confidential Transactions and More|date=2018|pages=315–334|doi=10.1109/SP.2018.00020|location=San Francisco, California|isbn=978-1-5386-4353-2|s2cid=3337741|doi-access=free}}</ref>
|2018
|Bulletproofs
|Da
|Da
|Nu
|Circuite aritmetice
|-
|Hyrax<ref>{{cite book|last1=Wahby|first1=Riad S.|last2=Tzialla|first2=Ioanna|last3=Shelat|first3=Abhi|last4=Thaler|first4=Justin|last5=Walfish|first5=Michael|title=2018 IEEE Symposium on Security and Privacy (SP)|chapter=Doubly-Efficient zkSNARKs Without Trusted Setup|date=May 2018|pages=926–943|doi=10.1109/SP.2018.00060|isbn=978-1-5386-4353-2|doi-access=free}}</ref>
|2018
|zk-SNARK
|Da
|Da
|Nu
|Circuite aritmetice
|-
|Halo<ref>{{cite journal|last1=Bowe|last2=Grigg|last3=Hopwood|first1=Sean|first2=Jack|first3=Daira|date=2019|title=Recursive Proof Composition without a Trusted Setup|url=https://eprint.iacr.org/2019/1021|journal=Cryptology ePrint Archive}}</ref>
|2019
|zk-SNARK
|Da
|Da
|Nu
|Circuite aritmetice
|-
|Virgo<ref>{{cite book|last1=Zhang|first1=Jiaheng|last2=Xie|first2=Tiancheng|last3=Zhang|first3=Yupeng|last4=Song|first4=Dawn|title=2020 IEEE Symposium on Security and Privacy (SP)|chapter=Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof|date=May 2020|pages=859–876|doi=10.1109/SP40000.2020.00052|isbn=978-1-7281-3497-0|doi-access=free}}</ref>
|2020
|zk-SNARK
|Da
|Da
|Da
|Circuite aritmetice
|-
|Ligero<ref>{{cite book|last1=Ames|first1=Scott|last2=Hazay|first2=Carmit|last3=Ishai|first3=Yuval|last4=Venkitasubramaniam|first4=Muthuramakrishnan|title=Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security|chapter=Ligero|date=30 October 2017|pages=2087–2104|doi=10.1145/3133956.3134104|chapter-url=https://dl.acm.org/doi/10.1145/3133956.3134104|publisher=Association for Computing Machinery|isbn=9781450349468|s2cid=5348527}}</ref>
|2017
|zk-SNARK
|Da
|Da
|Da
|Circuite aritmetice
|-
|Aurora<ref>{{cite book|last1=Ben-Sasson|first1=Eli|last2=Chiesa|first2=Alessandro|last3=Riabzev|first3=Michael|last4=Spooner|first4=Nicholas|last5=Virza|first5=Madars|last6=Ward|first6=Nicholas P.|title=Advances in Cryptology – EUROCRYPT 2019|chapter=Aurora: Transparent Succinct Arguments for R1CS|series=Lecture Notes in Computer Science|date=2019|volume=11476|pages=103–128|doi=10.1007/978-3-030-17653-2_4|chapter-url=https://link.springer.com/chapter/10.1007%2F978-3-030-17653-2_4|publisher=Springer International Publishing|isbn=978-3-030-17652-5|s2cid=52832327|language=en}}</ref>
|2019
|zk-SNARK
|Da
|Da
|Da
|Circuite aritmetice
|-
|zk-STARK<ref>{{cite book|last1=Ben-Sasson|first1=Eli|last2=Bentov|first2=Iddo|last3=Horesh|first3=Yinon|last4=Riabzev|first4=Michael|title=Advances in Cryptology – CRYPTO 2019|chapter=Scalable Zero Knowledge with No Trusted Setup|series=Lecture Notes in Computer Science|date=2019|volume=11694|pages=701–732|doi=10.1007/978-3-030-26954-8_23|chapter-url=https://link.springer.com/chapter/10.1007/978-3-030-26954-8_23|publisher=Springer International Publishing|isbn=978-3-030-26953-1|s2cid=199501907|language=en}}</ref>
|2019
|zk-STARK
|Da
|Da
|Da
|Limbaj de asamblare
|-
|Zilch<ref name="mouris212">{{cite journal|last1=Mouris|last2=Tsoutsos|first1=Dimitris|first2=Nektarios Georgios|date=2021|title=Zilch: A Framework for Deploying Transparent Zero-Knowledge Proofs|url=https://ieeexplore.ieee.org/document/9410618|journal=IEEE Transactions on Information Forensics and Security|volume=16|pages=3269–3284|issn=1556-6021|doi=10.1109/TIFS.2021.3074869|s2cid=222069813}}</ref>
|2021
|zk-STARK
|Da
|Da
|Da
|Orientat obiecte
|}

== Note ==
<references />

{{Control de autoritate}}
[[Categorie:Criptografie]]
[[Categorie:Demonstrații matematice]]
[[Categorie:Pagini cu traduceri nerevizuite]]