Objašnjeni dokazi o nulo znanju 2. dio: Neinteraktivni dokazi o nultom znanju

Primjer neinteraktivnog dokaza o nultom znanju: Sudoku i igraće karte

U prvom dijelu naše serije dokaza o nultom znanju objasnili smo kako dokazivanje nulteg znanja može djelovati kada verifikator i dokazivač međusobno djeluju.

Prednost interaktivnog dokaza o nultom znanju je u tome što samo ovjerivač može biti apsolutno uvjeren da dokazivač ima znanje. Ali to može biti i nedostatak.

Ako prolaznici i promatrači ne mogu potvrditi tvrdnju, ispitivač mora neovisno komunicirati sa svakim verifikatorom - za što je potrebno vrijeme i mnogo resursa.

U ovom ćemo dijelu 2 pogledati neinteraktivne dokaze o nultu znanju.

Neinteraktivni dokazi o nuli znanja

Razlog neinteraktivnog dokaza o nultom znanju je omogućavanje velikom broju promatrača da ga učinkovito provjere.

Ne moramo uvijek praviti dokaze o nuli znanja neinteraktivnim. Dovoljno često je moguće pronaći pouzdanog potvrđivača koji potvrđuje integritet dokaza.

Primjer neinteraktivnog dokaza o nultom znanju: Sudoku i igraće karte

Sudoku je igra različitih težina, ali relativno jednostavna pravila. Svaki od 9 redaka, 9 stupaca i 9 sektora (kako je naznačeno debelom crnom linijom) mora sadržavati svaki broj od 1 do 9 točno jedanput.

Zamislite da je rješenje sudoku slagalice posebno teško dobiti i trebati dane čak i superračunalo za izračun.

Ali netko (dokaznik) tvrdi da rješenje zagonetke ima i spreman je prodati za cijenu. Kako mogu dokazati da imaju rješenje - a da to ne otkrivaju - pa je verifikator spreman platiti?

Dokaz:

Dostavljaču je potrebno 27 igraćih karata (bilo kojeg odijela) s brojevima od 1-9—243.

Sada, dokazivač stavlja tri kartice s brojem koji odgovara ispravnom Sudoku rješenju u svaki okvir. E.G., ako je točan odgovor na kutiji 7, dokazivač će u njega staviti 3 karte za igru ​​sa vrijednošću 7.

Na tablici Sudokua vidjet će se neki odgovori. Na tim se odgovornim okvirima postavljaju karte za igranje licem prema gore. Na Sudoku kutije koje su prazne postavljaju se karte licem prema dolje.

Da biste dokazali da su karte za lice okrenute prema dolje, u ispravnom položaju (bez otkrivanja rješenja), dokazivač mora:

  • Uzmi gornju karticu od svakog red i napravite 9 gomila
  • Uzmi gornju karticu od svakog stupac i napravite 9 gomila
  • Preostale kartice uzmite od svake sektor i napravite 9 gomila

Prijave za dokaz o nule-znanju

Svaka se gomila pomiješa i okreće.

Svaki broj između 1-9 mora se pojaviti u svakom Sudoku retku, stupcu i sektoru. Dakle, ako svaka hrpa provjerenih karata (iz hrpa redaka, stupaca i sektora) sadrži svaku igračku kartu u vrijednosti 1-9, znamo da moraju imati rješenje.

Prijave za dokaz o nule-znanju

Doduše, relativno mlado polje dokaza o nultom znanju još nije pronašlo prihvaćanje koje bi to možda i zaslužilo. Međutim, mogu se pokazati vrlo vrijednim.

Mnogi su matematički problemi slični Sudoku zagonetki (na primjer problem Graphing Coloring). Ako uspijemo upotrijebiti gornji princip i uspješno ga primijeniti na različite probleme, možda ćemo moći efikasnije koristiti i trgovati računskim resursima i matematičkim problemima. Ili možda brže riješite matematičke poteškoće.

Kudovi su Ronenu Gradwohlu, Moni Naor, Bennyju Pinkasu i Guyu Rothblumu

Objašnjeni dokazi o nulo znanju 2. dio: Neinteraktivni dokazi o nultom znanju
admin Author
Sorry! The Author has not filled his profile.