Pojasnjeni dokazi z ničelnim znanjem 2. del: Neinteraktivni dokazila o ničelnem znanju

Primer neinteraktivnih dokazov o ničelnem znanju: Sudoku in igralne karte

V prvem delu naše serije ničelnega dokazila smo razložili, kako lahko dokaz z ničelnim znanjem deluje, ko sta preveritelj in dokaznik medsebojno komunicirala.

Prednost interaktivnega dokaza z ničelnim znanjem je v tem, da je samo preveritelj lahko popolnoma prepričan, da ima dokazilo znanje. Toda to je lahko tudi pomanjkljivost.

Če opazovalci in opazovalci ne morejo preveriti trditve, mora preizkuševalec neodvisno komunicirati z vsakim preveriteljem - kar zahteva čas in je veliko sredstev.

V tem delu 2. dela si bomo ogledali neinteraktivne dokaze o ničelnem znanju.

Neinteraktivni dokazila o ničelnem znanju

Razlog za neinteraktivne dokaze o ničelnem znanju je, da se številnim opazovalcem omogoči učinkovito preverjanje dokaza.

Vedno nam ni treba delati dokazov o ničelnem znanju neinteraktivno. Dovolj pogosto je mogoče najti zaupanja vrednega preveritelja, ki potrdi za celovitost dokazila.

Primer neinteraktivnih dokazov o ničelnem znanju: Sudoku in igralne karte

Sudoku je igra z različnimi zahtevnostmi, a sorazmerno preprosta pravila. Vsaka od 9 vrstic, 9 stolpcev in 9 sektorjev (kot je označeno z debelo črno črto) mora vsebovati vsako številko od 1 do 9 točno enkrat.

Predstavljajte si, da je rešitev sudoku uganke še posebej težko dobiti in trajati je treba dneve, da lahko izračuna tudi superračunalnik..

Toda nekdo (dokazilo) trdi, da ima rešitev uganke in ga je pripravljen prodati za ceno. Kako lahko dokažejo, da imajo rešitev - ne da bi jo razkrili - tako je preveritelj pripravljen plačati?

Dokaz:

Dokazilo potrebuje 27 igralnih kart (poljubnih oblek) s številkami 1-9-2243.

Zdaj je pregovor v vsako polje postavil tri karte s številko, ki ustreza pravilni rešitvi Sudoku. E.G., če je za polje pravilen odgovor 7, bo preizkuševalec vstavil 3 igralne karte z vrednostjo 7.

Na tabeli Sudoku bodo vidni nekateri odgovori. Na teh, v okencih z odgovori, so postavljene igralne karte soočiti. Na škatle Sudoku, ki so prazne, so kartice postavljene obrnjena navzdol.

Če želite dokazati, da so kartice obrnjene navzdol v pravem položaju (ne da bi razkrili rešitev), mora preizkuševalec:

  • Od vseh vzemite zgornjo kartico vrstica in naredite 9 pilotov
  • Od vseh vzemite zgornjo kartico stolpec in naredite 9 pilotov
  • Preostale karte vzemite od vsake sektor in naredite 9 pilotov

Vloge za dokazila o ničelnem znanju

Vsak kup nato premešamo in obrnemo.

Vsaka številka med 1-9 mora biti prikazana v vsaki vrstici, stolpcu in sektorju Sudoku. Če torej vsak kup proverskih kart (iz vrstic, stolpcev in sektorskih pilotov) vsebuje vsako igralno karto v vrednosti 1-9, vemo, da morajo imeti rešitev.

Vloge za dokazila o ničelnem znanju

Res je, da razmeroma mlado področje dokazov o ničelnem znanju še ni ugotovilo, da bi si ga lahko zaslužilo. Lahko pa se izkažejo za zelo dragocene.

Številni matematični problemi so podobni uganki Sudoku (na primer problem Graphing Color). Če lahko zgornje načelo uporabimo in ga uspešno uporabimo za različne težave, bomo morda lahko učinkoviteje uporabljali in trgovali z računalniškimi viri in matematičnimi težavami. Ali pa morda hitreje rešite matematične težave.

Kudos do Ronen Gradwohl, Moni Naor, Benny Pinkas in Guy Rothblum

Pojasnjeni dokazi z ničelnim znanjem 2. del: Neinteraktivni dokazila o ničelnem znanju
admin Author
Sorry! The Author has not filled his profile.