Vysvetlené dôkazy o nulových znalostiach Časť 2: Neinteraktívne dôkazy o nulových znalostiach

Príklad neinteraktívnych dôkazov nulových vedomostí: Sudoku a hracie karty

V časti 1 našej série dôkazov o nulových vedomostiach sme vysvetlili, ako môže dôkaz o nulových vedomostiach fungovať, keď medzi overovateľom a overovateľom navzájom spolupracujú..

Interaktívny dôkaz o nulových znalostiach má výhodu v tom, že iba overovateľ môže byť úplne presvedčený o tom, že osoba, ktorá vykonáva overovanie, má znalosti. Môže to však byť aj nevýhoda.

Ak okolostojaci a pozorovatelia nedokážu verifikovať nárok, musí poskytovateľ dokladu interagovať s každým overovateľom nezávisle - čo si vyžaduje čas a je náročné na zdroje.

V tejto časti 2 sa pozrieme na neinteraktívne dôkazy nulových znalostí.

Neinteraktívne dôkazy o nulových znalostiach

Dôvodom neinteraktívnych dôkazov o nulových znalostiach je umožniť veľkému počtu pozorovateľov účinne overiť dôkaz.

Nie vždy je potrebné, aby dôkazy o nulových znalostiach boli neinteraktívne. Často je možné nájsť dôveryhodného overovateľa, ktorý sa zasadzuje za integritu dôkazu.

Príklad neinteraktívnych dôkazov nulových vedomostí: Sudoku a hracie karty

Sudoku je hra s rôznymi ťažkosťami, ale pomerne jednoduchými pravidlami. Každý z 9 riadkov, 9 stĺpcov a 9 sektorov (označených hrubou čiernou čiarou) musí obsahovať každé číslo od 1 do 9 presne raz.

Predstavte si, že riešenie sudoku je mimoriadne ťažké získať, a výpočet superpočítača trvá niekoľko dní..

Niekto však tvrdí, že má riešenie hádanky a je ochotný ju predať za cenu. Ako môžu dokázať, že majú riešenie - bez jeho odhalenia - takže overovateľ je pripravený uskutočniť platbu?

Dôkaz:

Potvrditeľ potrebuje celkom 27 hracích kariet (všetkých kombinácií) očíslovaných 1-9-243.

Prover teraz vloží do každej škatule tri karty s číslom zodpovedajúcim správnemu riešeniu sudoku. E.G., ak je správna odpoveď pre políčko 7, poskytovateľ doloží 3 hracie karty s hodnotou 7.

Na stole Sudoku budú viditeľné niektoré odpovede. Na tieto, odpovedané políčka sú umiestnené hracie karty hlavu hore. Na prázdne políčka Sudoku sa karty umiestnia tvárou dolu.

Na preukázanie toho, že sú všetky karty na správnom mieste (bez odhalenia riešenia), musí skúšajúci:

  • Vezmite najvyššiu kartu zo všetkých riadok a vyrobíme 9 hromád
  • Vezmite najvyššiu kartu zo všetkých stĺp a vyrobíme 9 hromád
  • Vezmite zvyšné karty od všetkých sektor a vyrobíme 9 hromád

Žiadosti o dôkazy o nulových znalostiach

Každá hromada sa potom zamieša a otočí.

V každom riadku, stĺpci a sektore sudoku musí byť každé číslo od 1 do 9. Takže ak každá hromada proverských kariet (z hromád riadkov, stĺpcov a sektorov) obsahuje každú hraciu kartu v hodnote 1-9, vieme, že musí mať riešenie.

Žiadosti o dôkazy o nulových znalostiach

Relatívne mladá oblasť dôkazov o nulových vedomostiach ešte nepotvrdila akceptáciu, ktorú si môže zaslúžiť. Môžu sa však ukázať ako veľmi cenné.

Veľa matematických problémov je podobných sudoku Sudoku (napríklad problém s vyfarbením grafu). Ak dokážeme využiť uvedený princíp a úspešne ho aplikovať na rôzne problémy, mohli by sme efektívnejšie využívať a obchodovať s výpočtovými zdrojmi a matematickými problémami. Alebo možno vyriešte matematické quandary rýchlejšie.

Kudos Ronenovi Gradwohlovi, Moni Naorovi, Bennymu Pinkasovi a Guyovi Rothblumovi

Vysvetlené dôkazy o nulových znalostiach Časť 2: Neinteraktívne dôkazy o nulových znalostiach
admin Author
Sorry! The Author has not filled his profile.