Predstavljajte si, da imate nekaj koristnega znanja - morda skrivni recept ali ključ do šifre. Bi lahko prijatelju dokazali, da imate to znanje, ne da bi mu kaj razkrili? Računalniški znanstveniki so pred več kot 30 leti dokazali, da bi lahko, če bi uporabili tako imenovani dokaz nič znanja.
Za preprosto razumevanje te ideje predpostavimo, da želite prijatelju pokazati, da znate priti skozi labirint, ne da bi razkrili podrobnosti o poti. Labirint ste lahko preprosto prečkali v določenem času, medtem ko je bilo vašemu prijatelju prepovedano gledati. (Časovna omejitev je potrebna, ker lahko ob dovolj časa vsakdo sčasoma najde pot ven s poskusi in napakami.) Vaš prijatelj bi vedel, da lahko to storite, vendar ne bi vedel, kako.
Dokazila z ničelnim znanjem so v pomoč kriptografom, ki delajo s tajnimi informacijami, pa tudi raziskovalcem računalniške kompleksnosti, ki se ukvarjajo s klasifikacijo težavnosti različnih problemov. "Veliko sodobnih kriptografij temelji na predpostavkah kompleksnosti - na predpostavki, da je določene probleme težko rešiti, tako da je vedno obstajalo nekaj povezav med obema svetovoma," je dejal Claude Crépeau, računalniški znanstvenik na univerzi McGill. "Toda [ti] dokazi so ustvarili cel svet povezav."
Dokazila brez znanja spadajo v kategorijo, ki je znana kot interaktivna dokazila, zato če želite izvedeti, kako delujejo prvi, pomaga razumeti slednje. najprej opisano v članku računalniških znanstvenikov iz leta 1985 Šafi Goldwasser, Silvio Micali in Charles Rackoff, interaktivni dokazi delujejo kot zasliševanje: prek niza sporočil skuša ena stran (dokazovalec) prepričati drugo (preverjevalca), da je dana izjava resnična. Interaktivni dokaz mora izpolnjevati dve lastnosti. Prvič, resnična izjava bo na koncu vedno prepričala poštenega preveritelja. Drugič, če je dana izjava napačna, noben dokazovalec - tudi tisti, ki se pretvarja, da ima določeno znanje - ne more prepričati preveritelja, razen z zanemarljivo majhno verjetnostjo.
Interaktivni dokazi so po naravi verjetnostni. Dokazovalec bi lahko pravilno odgovoril na eno ali dve vprašanji zgolj po sreči, zato je potrebno dovolj veliko število izzivov, ki jih mora vse pravilno opraviti, da se preveritelj prepriča, da dokazovalec dejansko ve, da je izjava resnična.
Ta zamisel o interakcijah je prišla, ko sta se Micali in Goldwasser — takrat podiplomska študenta na kalifornijski univerzi v Berkeleyju — ugankala skozi logistiko igranja pokra prek omrežja. Kako lahko vsi igralci preverijo, da je rezultat naključen, ko eden od njih dobi karto iz virtualnega kompleta? Interaktivni dokazi bi lahko vodili. Toda kako lahko potem igralci preverijo, ali je bil celoten protokol – celoten nabor pravil – upoštevan pravilno, ne da bi pri tem razkrili roko vsakega igralca?
Da bi dosegla ta cilj, sta Micali in Goldwasser obema, potrebnima za interaktivni dokaz, dodala še tretjo lastnost: dokaz ne sme razkriti ničesar o samem znanju, le resničnost izjave. "Obstaja ideja, da greš skozi protokol, na koncu katerega verjameš, da [igralci pokra] ne vedo ničesar več od tistega, kar bi morali vedeti," je dejal Goldwasser.
Razmislimo o klasičnem primeru. Alice želi Bobu dokazati, da določen graf G — edinstvena zbirka vozlišč (pik), povezanih z robovi (črtami) — ima "Hamiltonov cikel." To pomeni, da ima graf pot, ki obišče vsako točko točno enkrat in se konča pri isti točki, s katere se je začela. Alice bi to lahko naredila tako, da bi Bobu preprosto pokazala pot, ki to naredi, seveda pa bi potem tudi on poznal pot.
Evo, kako lahko Alice prepriča Boba, da ve, da taka pot obstaja, ne da bi mu to pokazala. Najprej nariše nov graf, H, to ne izgleda tako G vendar je podoben na ključen način: ima enako število oglišč, povezanih na enak način. (Če G res ima Hamiltonov cikel, ta podobnost pomeni H bo tudi.) Potem, ko prekrijete vsak rob v H z lepilnim trakom se zaklene H v škatli in da škatlo Bobu. To mu preprečuje, da bi ga videl neposredno, vendar tudi njej preprečuje, da bi ga spremenila. Nato se Bob odloči: Ali lahko prosi Alice, da to pokaže H res je podoben G, lahko pa jo prosi, naj mu pokaže Hamiltonov cikel v H. Obe zahtevi bi morali biti za Alice enostavni, če to predpostavimo H je res dovolj podoben G, in da res pozna pot.
Seveda, tudi če Alice ne pozna Hamiltonovega cikla v G, lahko poskuša pretentati Boba bodisi z risanjem grafov, ki niso podobni G, ali z oddajo grafov, za katere ne pozna poti. Ko pa odigrata več krogov, postane možnost, da Alice vsakič prevara Boba, izginotno majhna. Če bo naredila vse v redu, bo Bob sčasoma prepričan, da Alice pozna Hamiltonov cikel v grafu G, ne da bi ga Bob sploh videl.
Po začetnem članku, ki je prvič opisal takšne dokaze, so Micali in dva matematika – Oded Goldreich in Avi Wigderson – odkrili nepričakovano posledico z daljnosežnimi učinki. Povezano je z glavno kategorijo problemov približno enake težavnosti, znano kot NP. Te težave je težko rešiti, vendar je njihove rešitve enostavno preveriti. Trije raziskovalci ugotovljeno, da je, če je šifriranje resnično varno mogoče, potem je rešitev vsake težave v NP mogoče dokazati tudi z ničelnim dokazom znanja. Ta študija je pomagala raziskovalcem zamisliti različice dokazov brez znanja, ki sploh ne zahtevajo varnega šifriranja; ti so znani kot interaktivni dokazi z več dokazilci.
In leta 1988, Micali in drugi je pokazala, če si dokazovalnik in verifikator delita kratek niz naključnih bitov, interakcija ni potrebna. To je teoretično pomenilo, da ni nujno, da so dokazi z ničelnim znanjem interaktivni, kar bi pomenilo, da stalna komunikacija med dvema stranema ni potrebna. To bi jih naredilo veliko bolj uporabne za raziskovalce, vendar so se takšni dokazi razširili šele po prelomu 21. stoletja.
"V poznem 2000-ih smo začeli opažati razvoj učinkovitih tehnik za izdelavo dokazov brez znanja," je dejal Matthew D. Green, kriptograf na univerzi John Hopkins. »Prišli smo do točke, ko smo ugotovili, 'Počakaj malo, morda dejansko obstaja način, da to uporabimo v praksi.'«
Zdaj lahko dokazovalnik pošlje eno sporočilo verifikatorju, ne da bi oba morala biti na spletu, raziskovalci pa bi lahko ustvarili zelo kratek dokaz, ki bi ga bilo mogoče hitro preveriti, tudi za zelo zapletene probleme. To je vodilo do več praktičnih uporab, kot je možnost hitrega preverjanja verige blokov po transakciji s kriptovaluto, medtem ko se podrobnosti transakcije skrivajo. In leta 2016 skupina fizikov je pokazala, kako lahko dokazi brez znanja pomagajo pri jedrski razorožitvi: ne da bi razkrili kakršno koli skrivnost o zasnovi svoje jedrske bojne glave, lahko država zdaj jedrskim inšpektorjem dokaže, ali je bojna konica aktivna ali neaktivna.
V zadnjem času je napredek v kvantnem računalništvu prisilil Crépeauja, da je stresno testiral pretekle raziskave, da bi zagotovil, da so protokoli brez znanja še vedno izvedljivi. Leta 2021 je pomagal izkazati da interaktivni dokazi z več dokazi sicer ohranijo svojo tajnost, tudi če so vključeni kvantni računalniki, vendar doseganje enake ravni varnosti povzroči, da je protokol veliko počasnejši. Ugotovitev je dobra novica, je dejal, vendar se bodo z napredkom tehnologije pojavili novi pomisleki.
"Vsaka vrsta računanja, ki ga lahko izvajamo v prihodnosti, bo vključevala kvantne računalnike," je dejal Crépeau. "Kot dobri paranoični kriptografi želimo vedno, ko ocenjujemo varnost sistema, zagotoviti, da je naš sistem varen."
Opomba urednika: Shafi Goldwasser je prejel sredstva od fundacije Simons, ki financira tudi to uredniško neodvisna publikacija. Odločitve o financiranju fundacije Simons nimajo vpliva na našo pokritost.
