O interaktivnim dokazima i nultom znanju: Priručnik

Zajednički rad sa Sebastianom Gajekom

Što možete očekivati ​​od pročitanog

  • Osnovno razumijevanje svojstava dokaznih sustava, uključujući nulte znanje, ispravnost i cjelovitost, a time i osnovna svojstva zkSNARKs, zkSTARKs ili zkNIZK
  • Paradigma simulacije, nerazlučivost računanja i izvlačenje svjedoka
  • Schnoor-ov protokol, uključujući izlog dokaza zvučnosti, nulte znanja i potpunosti
Slika akreditirana za Volkana Olmeza
Interaktivni dokazi bitni su pojmovi samog pojma provjerljivog računanja - moćan kriptografski alat za osiguranje računalne integriteta pametnog izvršenja ugovora, programa ili baze podataka. Ono što je najvažnije, teorija interaktivnih dokaza pruža zemlju za neinteraktivne dokaze o nulti znanju (NIZK), sažet neinteraktivni argument znanja (SNARKs) ili sažet transparentne argumente znanja (STARKs). U ovom ćemo članku opisati utemeljenu teoriju iza interaktivnih dokazanih sustava i nadamo se da ćemo olakšati ulazak pridošlima u vrlo uzbudljivo i obećavajuće polje SNARK-a i STARK-a.

1. Uvod

Nedavno su sustavi dokaza dokazali ogroman interes u kontekstu ocjene integriteta računanja. Na primjer, mogu pomoći u provođenju „kriptografskog“ revizora kako bi potvrdili da je matematička funkcija poput upita za pretraživanje nad bazom podataka doista izračunata, što podrazumijeva ispravnost izlaza s obzirom na potencijalno zlonamjernog vlasnika baze podataka. Nula-znanje je prekrasno svojstvo dokaznih sustava koji jamče privatnost izračuna. Omogućuje provjeru izračuna nad skupom podataka bez otkrivanja bilo kakvih djelomičnih podataka o podacima. U skladu s tim, sustavi sa nultim znanjem pronalaze primjenu u domenama osjetljivim na privatnost poput anonimne identifikacije, upita o učlanjenju baze podataka ili Blockchain plaćanja.

1.1 Što je dokazni sustav?

U teoriji složenosti računanja, interaktivni sustav dokazivanja je apstraktni stroj koji modelira računarstvo kao razmjenu poruka između dviju strana. Strane, poznate kao dokazani P i verifikator V, komuniciraju razmjenom poruka kako bi utvrdile da li je izjava točna.

Dokaz je svemoćan i posjeduje neograničene računske resurse, ali mu se ne može vjerovati, dok verifikator ima ograničenu računsku moć. Poruke se šalju između potvrđivača i provjere dok verifikator ne može potvrditi ili falsificirati izjavu. Svi interaktivni sustavi provjere imaju dva ključna svojstva:

Potpunost: ako je izjava istinita, iskren potvrđivač (to je onaj koji pravilno prati protokol) može biti uvjeren u tu činjenicu iskrenim dokazom.

Zvučnost: ako je izjava lažna, nijedan varanje / zlonamjerni dokaz ne može uvjeriti iskrenog provjeravača da je istinita, osim s nekom zanemarivom vjerojatnošću.

Drugim riječima, svojstvo zvuka potvrđuje da se postupak provjere dokaza ne može „prevariti“ u prihvaćanju lažnih izjava. Na taj način, zvučnost bilježi sposobnost verifikatora da se zaštiti od uvjerenja u lažne izjave (bez obzira na to što je dokaz učinio kako bi prevario provjerivača). S druge strane, kompletnost jednostavno obuhvaća sposobnost nekih dokaza koji uvjeravaju provjeriti istinite izjave (koje pripadaju nekom unaprijed određenom skupu istinitih izjava). Imajte na umu da su oba svojstva ključna za sam pojam sustava dokazivanja.

1.2 Privatnost putem nule-znanja

Sustavi dokazivanja bez znanja (interaktivni) imaju nevjerojatno dodatno svojstvo da ne donose ništa izvan valjanosti tvrdnje. Međutim, imajte na umu da vlasništvo ima smisla samo ako dostavljač ima tajne podatke - na zk-žargonu koji se naziva i svjedok - i želi da verifikator ne sazna nikakve djelomične podatke o njemu. Stoga se treće magično svojstvo dokaznih sustava može sažeti kao

Nulta saznanja: ako je izjava istinita, nijedan verifikator ne vara ništa osim ove činjenice.

U literaturi o nultom znanju kanonski je primjer za objašnjenje svojstva. U ovom primjeru nalazi se špilja čiji se put dijeli na dva. Ove dvije staze povezane su vratima koja se mogu otvoriti samo tajnom riječi. Jedna osoba, zvana Alice, želi dokazati drugoj osobi, Bobu, da ona zna tajnu riječ, a da je ne izda. Za to se obje stranke prvo postavljaju na ulazu u špilju. Tada Alice ulazi i slijedi jedan od dva staza - koji je do nje. Bob s ulaza ne može reći koji je put odabrala Alice.

Pećina Ali Babe u nuli-znanju

Tada Bob ulazi u pećinu i potrči do vilice. Odabere jednu od dvije staze i pozove je u špilju. Alicein zadatak je proći tim putem do Boba. Ako uspije, korak je bliže cilju dokazati Bobu da zna tajnu riječ.

Ako je Alice odabrala put koji je Bob odabrao, njoj ne trebaju tajne riječi. Samo ako je odabrala suprotan put, mora proći kroz vrata da bi krenula na pravi put. To znači da zlonamjerna Alice, koja nije svjesna tajne riječi, u jednom tekstu ovog protokola može uvjeriti Boba do 50%. (Zbog toga će Alice i Bob ponavljati protokol kako bi smanjili vjerojatnost pogreške zvuka.) Protokol je dokaz nule, jer koliko god puta Alice i Bob ponovili postupak, Alice će, ako zna tajnu riječ, uvijek raditi slijedite put koji je odabrao Bob. U međuvremenu, Bob ne saznaje ništa o tajni [1].

1.3 Kanonska primjena: sheme identifikacije

Jedna od prvih primjena interaktivnih dokaznih sustava s nultim znanjem bile su sheme identifikacije. U shemi identifikacije stranka, koja se zove dokazana Alice, želi uvjeriti drugu stranku, verifikatora Boba, da je to određena stranka. Ovaj postupak provjere identiteta entiteta sastojak je pružanja stranke određenoj usluzi, kao što je pristup najnovijim epizodama Games of Thrones, jer je davatelj sadržaja identificirao stranku kao premium člana. U tu svrhu stranka posjeduje tajnog svjedoka, kao što su kriptografski ključ ili lozinku, a nijedna druga strana uključujući davatelja sadržaja nije svjesna. Primjerimo sada tri svojstva u slučaju streaminga Games of Thrones.

  • Garancija potpunosti jamči da će Alice biti pretplatnik pretplatnika i ona će dobiti pristup premium sadržaju.
  • Čvrstoća jamči da nijedna druga strana ne može tvrditi da je Alice i dobiti pristup premium sadržaju.
  • Nula-znanje osigurava da nijedna druga strana, uključujući davatelja sadržaja, ne sazna tajnog svjedoka i može impresionirati Alicu u budućim identifikacijama. Pojam nulte znanja podrazumijeva da dokaz identiteta nije prenosiv.

Na dnu sheme identifikacije leži ideja da Alice zna neku tajnu (izravno povezanu s njenim identitetom) i ona dokazuje Bobu znanje o tajni. Da spriječite da zlonamjerni Bob ubuduće lažno predstavlja Alicu, očekujte od protokola da Bob ne sazna djelomične podatke o Aliceinoj tajni. Suprotno tome, stranka koja sebe lažno predstavlja Alice neće iznijeti valjan dokaz i dobiti pristup tokovima GoT-a.

2. Formalne definicije: Đavo je u detalju

Iako se svojstva dokaznog sustava mogu činiti intuitivnim, definiranje cjelovitosti, ispravnosti ili nulte znanja na strog i matematički zdrav način oduzelo je desetljećima istraživačku zajednicu. Da bismo formalizirali svojstva, trebat će nam model proračuna da bismo iskazali što je interakcija dvaju računalnih uređaja. U kriptografiji se preferirani izbor daje Turingovim strojevima nazvanim po "ocu" informatike Alanu Turingu.

2.1 Interaktivni Turingov stroj

Interaktivni Turingov stroj (ITM) je (deterministički) Turingov uređaj s više vrpca (vidi sliku 1). Kasete su ulazna traka samo za čitanje, slučajna traka samo za čitanje, radna traka za čitanje i pisanje, izlazna traka za samo pisanje, komunikacijske vrpce i preklopna vrpca za čitanje i pisanje koja se sastoji od jedna ćelija. Jedna komunikacijska vrpca je samo za čitanje, a druga samo za pisanje. Svakom ITM-u pridružen je jedan bit, koji se naziva njegov identitet. Kaže se da je ITM aktivan u konfiguraciji, ako je sadržaj njegove prekidačke trake jednak identitetu računala. Inače se kaže da stroj miruje. Stanje stroja, položaj njegovih glava na raznim vrpcama i sadržaj upisnih vrpci ITM-a ne mijenjaju se u stanju mirovanja.

Slika 1: Ilustracija dvaju interaktivnih strojeva za turing.

Sadržaj ulazne vrpce naziva se ulazni, sadržaj slučajne vrpce naziva se slučajnim ulazom, a sadržaj izlazne vrpce na kraju se naziva izlaz. Sadržaj napisan na komunikacijskoj vrpci samo za pisanje tijekom (vremenskog) razdoblja u kojem je stroj aktivan naziva se porukom koja je poslana u tom razdoblju. Isto tako, sadržaj koji se tijekom aktivnog razdoblja čita s vrpce za čitanje samo za čitanje naziva se primljenom porukom (u tom razdoblju). (Bez gubitka općenitosti, strojni pokreti na obje komunikacijske vrpce idu u samo jednom smjeru, npr. S lijeva na desno.)

Sada možete nazvati interaktivni stroj za podešavanje M₁ dokazao P, a M₂ verifikator V, respektivno. Kao i ljudi, i strojevi moraju razumjeti jezik L da bi pravilno komunicirali. Ovdje ne planiramo duboko zaroniti u jezičnu teoriju i složenost. Sve što trebamo znati jest da izjava koju dokaz P želi dokazati mora biti - vrlo slabo rečeno - kodirana na određenom jeziku. Sa (x, w) ∈ L i (x, w) ∉ L izražavamo ispravnu / netočnu dokaznu tvrdnju ili drugim riječima par (x, w) je član jezika L. Obično je vrijednost x javna i poznat i dokazivaču i potvrđivaču, a parametar w (koji se naziva svjedok) je privatan i poznat samo onom koji je dokazao.

Formalno je jezik L definiran kao skup (možda beskonačno) nizova preko neke konačne abecede i formirani su prema određenom skupu pravila. Na primjer, jezik L iznad abecede Σ = {0, 1, 2, -, =} može imati sljedeću gramatiku:

  • Svaki ne prazni niz koji ne sadrži "-" ili "=" i ne počinje s "0" nalazi se u L
  • Niz koji sadrži "=" nalazi se u L ako i samo ako postoji točno jedan "=", a on razdvaja dva valjana niza L

Prema ovim pravilima, niz "2-1 = 1" nalazi se u L, ali niz "= 21 = 0-" nije. Tijekom faze postavljanja komunikacijskog protokola, stranke koje komuniciraju često se dogovaraju o određenom jeziku s određenim pravilima.

2.2 Interaktivni sustavi provjere

Par interaktivnih uređaja za turing (P, V) naziva se interaktivni sustav dokazivanja za jezik L ako je stroj V polinomno vrijeme i vrijede sljedeća dva uvjeta:

  • Potpunost: Za sve (x, w) u jeziku L značajna je vjerojatnost da dokazivač P može uvjeriti poštenog potvrđivača V. To je,
∀ (x, w) ∈ L: Pr [⟨P (x, w), V (x)⟩ = 1] ≤ 1 - negl
  • Zvučnost (slaba inačica, također, neizreciva): Za sve (x, w) koji nisu na jeziku L, vjerojatnost da varanje P može uvjeriti iskrenog potvrđivača V zanemariva je. To je,
∀ (x, w) ∉ L: Pr [⟨P '(x), V (x)⟩ = 1] ≤ negl
  • Posebna zvučnost (snažna verzija pod nazivom Izdvajanje znanja):

Za svaki (x, w) u jeziku L postoji algoritam polinomnog vremena E (ekstraktor) tako da se svjedok w može izvući iz valjanih razgovora s dokazivačem P i verifikatorom V. To jest

∀ (x, w) ∈ L, ∃ E: Pr [E⟨P (x, w), V (x)⟩ = w] ≤ 1 - negl

Zvuk dolazi u dva okusa. Slabiji pojam zvuka pomalo otkriva intuiciju svojstva nezamislivosti. Zapravo dokazni sustavi i digitalni potpisi imaju mnogo toga zajedničkog. Preko Fiat-Shamir transformacije se može pretvoriti klasa protokola poznata kao Sigma protokoli u digitalni potpis. O tehnici raspravljamo u narednom članku. Jači pojam često se naziva i imovinom za izvlačenje svjedoka. Protokoli koji zadovoljavaju svojstvo nazivaju se dokazima znanja. U osnovi je postojanje okvira za izvlačenje na algoritamski način ideja računalnog znanja. Pretpostavimo da dokazi P poznaje svjedoka w. Tada je zacijelo koristila svjedoka tijekom izvođenja protokola (i tako ga nekako šifrirala u poruke protokola) kako bi uspjela uvjeriti provjeritelja. Pretpostavimo da imamo čarobnog anđela, izvlačiča, koji gleda stražnju stranu P i svjedoči o korištenju svjedoka u izvođenju protokola. Jasno je da bi to pokazalo snažan dokaz poznavanja svjedoka. U računarskom svijetu anđeli nažalost ne postoje. Umjesto toga, P i V su Turingovi strojevi, a isto tako i ekstraktor E. Da bismo uhvatili intuiciju „gledanja P-ovih leđa“, puštamo ekstraktora da izračuna svjedoka iz promatranja interakcije dokaza i P-a. ako možeš izvući svjedoka iz P-a, to je nekako moralo biti tamo. Ovdje se mora naglasiti da jednostavno pasivno prisluškivanje interakcije ne propušta nikakve djelomične podatke o svjedoku. U suprotnom, verifikator V uči svjedoka w i protokol teško zadovoljava bilo koji oblik nulte znanja. Ekstraktor E (za razliku od verifikatora) stoga mu je dodatna snaga! U sljedećem primjeru u nastavku primijetit ćemo da je dodatna snaga sposobnost premotavanja provjere P. Premotavanje je tehnika koja odražava srž ideje ideja: Jedan se program može izvoditi više puta (razmišljati o pozivanju funkcije) i ispisuje deterministički ishod, ako netko kontrolira nasumične vrpce / ulaze programa. Gledajući unaprijed, premotavanje dokaza P (konkretno, dva puta izvršavanje Schnorrovog protokola, dok je preusmjeravanje dokaza u određeno stanje prije drugog izvršenja) dovoljno je da se prikupe sve relevantne informacije za izvlačenje svjedoka. Ponovno imajte na umu da verifikator mora nedostajati dodatna snaga protokola da bi protokol zadovoljio nulte znanje.

  • Nulta znanja: Za svaki (x, w) na jeziku L postoji za sve verifikatore simulator S, tako da nijedan različivač polinomskog vremena D ne može razlikovati izvršavanje simuliranog protokola od izvršenja stvarne interakcije između dokaza P i potvrđivač V. To je
∀ (x, w) ∈L, ∀V ∃S: Pr [D⟨P (x, w), V (x)⟩ = 1] - Pr [D⟨S (x)⟩ = 1] ≤ negl

Prvo se moramo prisjetiti samog pojma računalne nerazlučivosti da bismo razumjeli mehanizam simulacije. Nerazlučivost je moćan koncept u brojnim područjima informatike. To je formalizirano učinkovito izračunavim algoritmom za donošenje odluka, razlikovnim brojem D, koji na ulazu niza uzorkovanog iz bilo kojeg od dva skupa mora odlučiti iz kojeg je skupa uzet. Razmotrite radi lakšeg izlaganja sljedeći mentalni eksperiment. Pretpostavimo da su čovjek i stroj koji simulira čovjeka skriveni iza zavjesa u kazalištu, a publika interaktivno djeluje s bilo koje od njih dvoje kroz zavjesu. Nakon dugog razgovora, ako publika ne može razdvojiti čovjeka od stroja (recimo da smo imali odluku 50:50), zaključili bismo da je stroj "dobar kao" ili "zvuči / izgleda / ponaša se kao" čovjek.

Sada razmotrimo slučaj gdje uspoređujemo interakciju dokaza i P i verifikatora V s izvršenjem koje simulator S proizvodi sa sljedećim upozorenjem. U stvarnoj interakciji između ispitivača i potvrđivača, P eksplicitno koristi svoje svjedočenje w, dok se simulatoru S daju samo javni podaci x. Unatoč nedostatku informacija, pretpostavimo da simulator izrađuje transkript koji "izgleda" kao interakcija između provere i verifikatora (vidi sliku 2).

Slika 2: Ilustracija pojma nulta znanja.

Tada mora biti slučaj da pravi transkript protokola propušta onoliko podataka koliko simulirani transkript. Imajte na umu da mora biti takav. U suprotnom, pogubljenja su se razlikovala. Međutim, po konstrukciji, simulirani transkript je nula znanja: ne propušta se djelomične informacije o svjedoku w. U stvari, simulator uopće ne može procuriti nikakve informacije jer nije u posjedu svjedoka. Zaključak je da stvarni transkript protokola također ne propušta nikakve podatke o svjedoku, jer je simulirani transkript nerazlučiv, odnosno dobar je kao i stvarni. Otuda je pravi protokol nula znanja.

3. Schnorrov protokol pod nazivom "Pozdrav svijet" Iskren sustav provjere nulteg znanja

Jedan od najjednostavnijih i najčešće korištenih dokaza znanja, dokaz poznavanja diskretnog logaritma, zaslužan je za Clausa P. Schnorra. Bio je njemački matematičar i kriptograf. Njegov protokol ima tri kruga i definiran je u cikličkoj skupini G reda q s generatorom g. Da bi se pokazalo da je nula znanja jezik L = {(x, w): x = gʷ} gdje je svjedok teško izračunati diskretni eksponent dnevnika, ispitivač djeluje s verifikatorom kao što je prikazano na slici 3.

3.1 Specifikacija sustava dokaza

Slika 3: Schnorrov protokol. Napominjemo da postoji nekoliko varijanti protokola. Radije biramo verziju protokola gdje je izazov e uzorkovan od {0, .., q-1}.

Postaviti:

  • Dokaz P ima tajni ulaz w i javni ulaz x = gʷ.
  • Verifikator V ima samo javni unos x = gʷ.
  • I P i V imaju zajedničke parametre javne skupine g i q.

Protokol:

  1. Dokaz P stvara slučajni element grupe h i uzorkuje slučajni cijeli broj r. Šalje slučajnu vrijednost a = gʳ verifikatoru V.
  2. Verifikator V odabire slučajni izazov e ∈ {0, .. q-1} i šalje ga ispitivaču P.
  3. Dokažite P odgovore na izazov s odgovorom z = r + ew.
  4. Verifikator V prihvaća odgovor (i time je uvjeren u dokaz), ako i samo ako je gᶻ jednak axᵉ.

3.2. Sigurnosna analiza

Sada analiziramo Schnorr-ov dokazni sustav i tvrdimo da ispunjava gornja svojstva.

Kompletnost je prikazana jednostavnom formulacijom ekvivalencije:

∀r, e: gᶻ = gʳ⁺ᵉʷ = gʳ (gʷ) ᵉ = axᵉ

Posebna zvučnost prikazana je na slici 4 konstruirajući ekstraktor E koji izračunava ispravni svjedok w i tako razbija pretpostavku diskretnog dnevnika (naime, pretpostavlja se da je računski težak problem za izračunavanje svjedoka w dan x = gʷ), čime se krši slabo svojstvo zvučnosti. Drugim riječima, smanjujemo zvučnost protokola na diskretni problem dnevnika uz pomoć ekstraktora E.

Slika 4: Ilustracija simulacijskog tijeka tijekom dokaza za posebnu zvučnost.

Da bi ekstrakcija djelovala, E pokreće dvije instance dokaza, označene kao P i P *. Tijekom simulacije, izvlačivač djeluje kao verifikator V za dva slučaja i izračuna svjedoka pomoću sljedeće strategije:

  1. Ekstraktor E hrani prvu dokaznu jedinicu P javnim unosom x = gʷ (i slučajnim kovanicama r da parametrizira svoje slučajne vrpce) i čeka da primi prvu provernu poruku a = gʳ.
  2. Ekstraktor E odabire slučajni bit e ∈ {0, .. q-1}, šalje e na dokazi P i čeka da dobije odgovor z = r + ew.
  3. Sada se premotava potvrda P na korak 2. (Tehnički ekstraktor poziva drugu provernu instancu P * s identičnim ulazom (x, r). Činjenica da prizivamo prover s istim slučajnošću r osigurava da ona čini isto (slučajno ) izbor kao i P za prvu poruku a. Stoga smo preokrenuli P.)
  4. Ekstraktor E odabire drugačiji e ', šalje ga na P * i čeka primanje odgovora z' = r + e'w.
  5. Napokon, svjedok će se izvući računanjem razlika parova na izazov i odgovor.
(z-z ') / (e-e') = ((r + ew) - (r + e'w)) / (e-e ') = (e-e') / (e-e ') · W = w

Nulti znanje: Protokol se smatra nultim znanjem ako za bilo koji verifikator V postoji simulator koji može stvoriti razgovore s istom raspodjelom kao i razgovori između provjeravatelja i verifikatora. Naglašavamo da Schnorrov protokol (kao što je gore navedeno) NIJE znanje nula. Razlog leži u nemogućnosti konstruiranja simulatora za sve provjere: Simulacija nedostaje zlonamjernim verifikatorima s nepredvidivim odabirom poruke e. Da bi simulacija prošla, simulator mora unaprijed pogoditi izazov. S obzirom na eksponencijalni prostor uzorkovanja e, izgledi za ovaj događaj su zanemarivi.

Schnorrov protokol zadovoljava, međutim, slabiji pojam privatnosti poznat kao pošten verifikator nulteg znanja. U ovom modelu verifikator slijepo slijedi izvršenje protokola i ne odstupa od gornjih specifikacija protokola. U okviru ovog pojednostavljenja, simulator više ne treba predvidjeti proizvoljno i na taj način teško predvidjeti ponašanje verifikatora. Umjesto toga, simulator sada može simulirati slučajni izbor poruke o izazovu e prije vremena, jer bi se - po pretpostavci - iskren verifikator ponašao upravo tako. Moguće je čak uzeti bilo koju vrijednost e, a zatim proizvesti razgovor u kojem se e pojavljuje kao izazov. Drugim riječima, simulator ne mora inzistirati na odabiru e, može uzeti e-vrijednost kao ulaz. To čini simulaciju jačom, jer pokazuje nulti znanje u prisutnosti statički oštećenih verifikatora. Da bismo to vidjeli, konstruiramo simulator S s obzirom na javni ulaz x = gʷ na sljedeći način:

  1. Simulator S odabire z jednoliko nasumično i izazov će pošteni verifikator V izdati.
  2. Simulator S izračunava početnu poruku provere kao a = gᶻ / xᵉ. Nadalje simulira poruku o izazovu verifikatora s e.
  3. Konačno, simulator S simulira treću poruku z.

Analizirajući simulaciju, vidimo da simulator S stvara valjanu interakciju ispitivača i ispitivača. Verifikator prihvaća simulirane protokolarne poruke jer se tako drži

a · xᵉ = (gᶻ / xᵉ) · xᵉ = gᶻ

Simulacija (a, e, z) ima potpuno istu raspodjelu vjerojatnosti kao i stvarni razgovori između poštenog dokaza i poštenog potvrđivača. (Iako ostaje za dokazati.)

4. Zaključak i izgledi o Sigma-protokolima i NIZK-ovima

Moglo bi se tvrditi da iskreno provjeravanje nulte znanja nije korisno svojstvo, jer u praksi nema smisla pretpostavljati da je provjernik iskren. Stvar je, međutim, da se protokoli s tim slabijim svojstvom mogu često koristiti kao građevni blokovi u konstrukcijama koje su doista sigurne protiv aktivnog varanja, kao što ćemo vidjeti. Protokoli koji imaju istu strukturu u tri poteza (opredjeljenje, izazov, odgovor) kao što je Schnorrov protokol nazivaju se Σ-protokoli. Postoje učinkoviti Sigma protokoli za dokazivanje različitih izjava, poput onih koje se odnose na diskretne logaritme. Štoviše, kroz Fiat-Shamir transformaciju, oni se učinkovito mogu pretvoriti u ne-interaktivni dokaz o nultom znanju (NIZK).

O Sigma-protokolima, Fiat-Shamir transformaciji planiramo pisati uz neke konkretne primjere NIZK konstrukcija u sljedećem članku. Ostanite u toku!

Daljnje čitanje

Teorija interaktivnih dokazanih sustava daleko je razrađena od onoga što smo tretirali u ovom članku. Evo popisa radova koji preporučujemo zaroniti dublje u ovo uzbudljivo polje.

  • Claus P. Schnorr: Učinkovito generiranje potpisa za pametne kartice. Journal of Cryptology, 4 (3): 239–252, 1991.
  • Mihir Bellare i Oded Goldreich: O definiranju dokaza znanja. Crypto'92.
  • Oded Goldreich: Temelji kriptografije - osnovni alati. Cambridge University Press, 2001.