miniatura|Un exemplu de peșteră pentru un protocol simplu cu cunoștințe zero. Î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. 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.
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. 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 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. În practică, aceste demonstrații se bazează pe ipoteze de calcul (de obicei, rezistența la coliziune a unei funcții hash criptografice ).
Exemple abstracte
Peștera lui Ali Baba
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”. 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 20, sau 9,56 × 10 −7.
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 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.
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.
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ă.
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.
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.
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
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ă.