Imaginați-vă că aveți cunoștințe utile - poate o rețetă secretă sau cheia unui cifr. Ai putea dovedi unui prieten că ai acele cunoștințe, fără să dezvălui nimic despre asta? Informaticii au dovedit cu peste 30 de ani în urmă că ai putea, dacă ai folosi ceea ce se numește o dovadă a cunoștințelor zero.
Pentru o modalitate simplă de a înțelege această idee, să presupunem că vrei să-i arăți prietenului tău că știi să treci printr-un labirint, fără a divulga niciun detaliu despre cale. Ai putea pur și simplu să traversezi labirintul într-un interval de timp, în timp ce prietenului tău i-a fost interzis să vizioneze. (Limitul de timp este necesar pentru că, având suficient timp, oricine își poate găsi în cele din urmă calea de ieșire prin încercare și eroare.) Prietenul tău ar ști că poți face asta, dar nu ar ști cum.
Dovezile cu cunoștințe zero sunt utile criptografilor, care lucrează cu informații secrete, dar și cercetătorilor de complexitate computațională, care se ocupă cu clasificarea dificultății diferitelor probleme. „O mulțime de criptografie modernă se bazează pe ipoteze de complexitate – pe ipoteza că anumite probleme sunt greu de rezolvat, așa că au existat întotdeauna unele conexiuni între cele două lumi”, a spus Claude Crépeau, un informatician la Universitatea McGill. „Dar [aceste] dovezi au creat o întreagă lume de conexiune.”
Dovezile cu cunoștințe zero aparțin unei categorii cunoscute sub numele de dovezi interactive, așa că pentru a afla cum funcționează primele, vă ajută să înțelegeți pe cele din urmă. Primul descris într-o lucrare din 1985 a informaticienilor Shafi Goldwasser, Silvio Micali și Charles Rackoff, dovezile interactive funcționează ca o interogație: pe parcursul unei serii de mesaje, o parte (dovatorul) încearcă să-l convingă pe cealaltă (verificatorul) că o anumită afirmație este adevărată. O dovadă interactivă trebuie să satisfacă două proprietăți. În primul rând, o declarație adevărată va convinge întotdeauna un verificator onest. În al doilea rând, dacă afirmația dată este falsă, niciun probator - chiar și unul care pretinde că posedă anumite cunoștințe - nu poate convinge verificatorul, cu excepția unei probabilități neglijabil de mică.
Dovezile interactive sunt de natură probabilistică. Dovatorul ar putea să răspundă corect la una sau două întrebări pur și simplu din noroc, așa că este nevoie de un număr suficient de mare de provocări, toate pe care probatorul trebuie să le înțeleagă corect, pentru ca verificatorul să devină încrezător că acesta știe de fapt că afirmația este adevărată.
Această idee a interacțiunilor a venit atunci când Micali și Goldwasser – pe atunci studenți absolvenți de la Universitatea din California, Berkeley – s-au nedumerit prin logistica jocului de poker într-o rețea. Cum pot toți jucătorii să verifice că atunci când unul dintre ei primește o carte din pachetul virtual, rezultatul este aleatoriu? Dovezile interactive ar putea deschide calea. Dar atunci, cum pot jucătorii să verifice dacă întregul protocol - setul complet de reguli - a fost respectat corect, fără a dezvălui mâna fiecărui jucător pe parcurs?
Pentru a atinge acest obiectiv, Micali și Goldwasser au adăugat o a treia proprietate celor două necesare pentru o demonstrație interactivă: Dovada nu ar trebui să dezvăluie nimic despre cunoașterea în sine, doar veridicitatea afirmației. „Există o noțiune de a trece printr-un protocol, la sfârșitul căruia crezi că [jucătorii de poker] nu știu nimic mai mult decât ceea ce ar trebui să știu”, a spus Goldwasser.
Să luăm în considerare exemplul clasic. Alice vrea să-i demonstreze lui Bob că un anumit grafic G — o colecție unică de vârfuri (puncte) conectate prin margini (linii) — are un „ciclu hamiltonian”. Aceasta înseamnă că graficul are o cale care vizitează fiecare punct exact o dată și se termină în același punct din care a început. Alice ar putea face asta arătându-i lui Bob calea care face asta, dar bineînțeles că atunci ar ști și el calea.
Iată cum îl poate convinge Alice pe Bob că știe că o astfel de cale există, fără să i-o arate. Mai întâi ea desenează un nou grafic, H, asta nu pare G dar este similar într-un mod crucial: are același număr de vârfuri, conectate în aceleași moduri. (Dacă G are într-adevăr un ciclu hamiltonian, înseamnă această asemănare H va de asemenea.) Apoi, după ce a acoperit fiecare margine în H cu bandă de mascare, ea încuie H într-o cutie și îi dă cutia lui Bob. Acest lucru îl împiedică să o vadă direct, dar o împiedică și pe ea să o modifice. Apoi Bob face o alegere: fie îi poate cere Alicei să arate asta H într-adevăr este asemănător cu G, sau îi poate cere să-i arate ciclul hamiltonian în H. Ambele cereri ar trebui să fie ușoare pentru Alice, presupunând că H într-adevăr este suficient de asemănător cu Gși că ea chiar cunoaște calea.
Desigur, chiar dacă Alice nu cunoaște ciclul hamiltonian în G, ea poate încerca să-l păcălească pe Bob, fie desenând grafice care nu sunt asemănătoare cu G, sau trimițând grafice pentru care nu știe calea. Dar după ce au jucat mai multe runde, șansa ca Alice să-l înșele pe Bob de fiecare dată devine extrem de mică. Dacă ea înțelege totul bine, în cele din urmă Bob va fi convins că Alice cunoaște un ciclu hamiltonian în grafic G, fără ca Bob să fi văzut vreodată.
După lucrarea inițială care a descris pentru prima dată astfel de dovezi, Micali și doi matematicieni - Oded Goldreich și Avi Wigderson - au descoperit o consecință neașteptată cu efecte de anvergură. Are de-a face cu o categorie majoră de probleme de dificultate aproximativ egală, cunoscută sub numele de NP. Aceste probleme sunt greu de rezolvat, dar soluțiile lor sunt ușor de verificat. Cei trei cercetători a constatat că, dacă criptare cu adevărat sigură este posibil, atunci soluția fiecărei probleme din NP poate fi demonstrată și cu o demonstrație cu cunoștințe zero. Acest studiu a ajutat cercetătorii concepe variante de dovezi de zero cunoștințe care nu necesită nici măcar criptare sigură în primul rând; acestea sunt cunoscute sub numele de dovezi interactive cu mai multe probe.
Și în 1988, Micali și alții a arătat că, dacă un probator și un verificator împărtășesc un șir scurt de biți aleatori, nu este necesară nicio interacțiune. Acest lucru însemna teoretic că dovezile de cunoștințe zero nu trebuie să fie interactive, ceea ce ar implica că nu este necesară comunicarea constantă între două părți. Acest lucru le-ar face mult mai utile cercetătorilor, dar abia după începutul secolului al XXI-lea astfel de dovezi au luat amploare.
„La sfârșitul anilor 2000, am început să vedem evoluția tehnicilor eficiente de construire a dovezilor cu cunoștințe zero”, a spus Matthew D. Green, criptograf la Universitatea John Hopkins. „Am ajuns la punctul în care ne-am dat seama: „Stai o secundă, ar putea exista o modalitate de a folosi acest lucru în practică.”
Acum, un probator ar putea trimite un singur mesaj unui verificator fără ca ambii să fie online, iar cercetătorii ar putea crea o dovadă foarte scurtă care ar putea fi verificată rapid, chiar și pentru probleme foarte complicate. Acest lucru a condus la mai multe utilizări practice, cum ar fi capacitatea de a verifica rapid blockchain-ul după o tranzacție cu criptomonede, ascunzând detaliile tranzacției. Și în 2016, un grup de fizicieni a arătat modul în care dovezile fără cunoștințe pot ajuta la dezarmarea nucleară: fără a dezvălui niciun secret despre proiectarea focosului său nuclear, o țară le-ar putea dovedi acum inspectorilor nucleari dacă focosul este activ sau inactiv.
Mai recent, progresele în calculul cuantic l-au determinat pe Crépeau să testeze cercetările anterioare pentru a se asigura că protocoalele de zero cunoștințe sunt încă viabile. În 2021, a ajutat demonstra că dovezile interactive cu dovezi multiple își păstrează secretul chiar și atunci când sunt implicate computere cuantice, dar atingerea aceluiași nivel de securitate face ca protocolul să fie mult mai lent. Descoperirea a fost o veste bună, a spus el, dar noi preocupări vor apărea pe măsură ce tehnologia avansează.
„Orice tip de calcul pe care îl putem face în viitor va implica computere cuantice”, a spus Crépeau. „Deci, în calitate de buni criptografi paranoici, de fiecare dată când evaluăm securitatea unui sistem, vrem să ne asigurăm că sistemul nostru este în siguranță.”
Nota editorului: Shafi Goldwasser a primit finanțare de la Fundația Simons, care finanțează și aceasta publicație independentă editorial. Deciziile de finanțare ale Fundației Simons nu au nicio influență asupra acoperirii noastre.
