Zināšanu bez pierādījumiem skaidrojums 2. daļa: Neinteraktīvi nulles zināšanu pierādījumi

Mūsu nulles zināšanu pierādīšanas sērijas 1. daļā mēs paskaidrojām, kā nulles zināšanu pierādījums varētu darboties, ja verificētājs un sakāmvārds mijiedarbojas viens ar otru..

Interaktīvam nulles zināšanu pierādījumam ir tāda priekšrocība, ka tikai verificētājs var būt pilnīgi pārliecināts, ka zinātājam ir zināšanas. Bet tas var būt arī trūkums.

Ja apkārtējie un novērotāji nevar pārliecināties par apgalvojumu, tad prover ir mijiedarbojas ar katru verificētāju neatkarīgi – tas prasa laiku un prasa daudz resursu.

Šajā 2. daļā mēs apskatīsim neinteraktīvus nulles zināšanu pierādījumus.

Neinteraktīvi nulles zināšanu pierādījumi

Neinteraktīvo nulles zināšanu pierādījumu iemesls ir ļaut lielam skaitam novērotāju efektīvi pārbaudīt pierādījumus.

Mums ne vienmēr ir jāpadara nulles zināšanu pierādījumi neinteraktīvi. Pietiekami bieži ir iespējams atrast uzticamu verificētāju, kurš garantē pierādījuma integritāti.

Neinteraktīvu nulles zināšanu pierādījumu piemērs: Sudoku un spēļu kārtis

Sudoku ir spēle ar dažādām grūtībām, bet samērā vienkāršiem noteikumiem. Katrā no 9 rindām, 9 kolonnām un 9 sektoriem (kā norāda biezā melnā līnija) jābūt katram skaitlim no 1 līdz 9 precīzi vienu reizi..

Iedomājieties, ka sudoku mīklas risinājumu ir īpaši grūti iegūt, un pat superdatora aprēķins prasa vairākas dienas.

Bet kāds (senvārds) apgalvo, ka viņam ir puzles risinājums, un vēlas to pārdot par cenu. Kā viņi var pierādīt, ka viņiem ir risinājums – neatklājot to -, lai verificētājs būtu gatavs veikt maksājumu?

Pierādījums:

Prover ir vajadzīgas 27 spēļu kārtis (jebkura masta), kuru kopējais skaitlis ir 1-9–243.

Tagad sakāmvārds katrā lodziņā ievieto trīs kārtis ar numuru, kas atbilst pareizam Sudoku risinājumam. E. G., ja lodziņā pareizā atbilde ir 7, sakāmvārds tajā ievietos 3 spēļu kārtis ar vērtību 7.

Uz Sudoku galda būs redzamas dažas atbildes. Uz šīm atbildētajām kastēm tiek ievietotas spēļu kārtis seju uz augšu. Tukšās sudoku kastēs kartes tiek ievietotas seju uz leju.

Lai pierādītu, ka visas atklātās kartes ir pareizajā stāvoklī (neatklājot risinājumu), sakāmvārdam:

• Paņemiet labāko karti no katra rinda un izveidojiet 9 pāļus
• Paņemiet labāko karti no katra sleja un izveidojiet 9 pāļus
• Paņemiet atlikušās kārtis no visām sektors un izveidojiet 9 pāļus

Pēc tam katru kaudzi samaisa un apgriež.

Katram skaitlim no 1-9 jābūt parādītam katrā Sudoku rindā, kolonnā un sektorā. Tātad, ja katrā sakāmvārda kāršu kaudzē (no rindas, kolonnas un sektora kaudzēm) ir katra spēļu kārts ar vērtību 1-9, mēs zinām, ka tām ir jābūt risinājumam.

Pieteikumi nulles zināšanu pierādījumiem

Jāatzīst, ka salīdzinoši jaunais nulles zināšanu pierādījumu lauks vēl nav atradis piekrišanu tam, ko tas varētu būt pelnījis. Tomēr tie varētu izrādīties ļoti vērtīgi.

Daudzas matemātiskas problēmas ir līdzīgas Sudoku mīklai (piemēram, grafika krāsošanas problēma). Ja mēs varam izmantot iepriekš minēto principu un veiksmīgi to piemērot dažādām problēmām, mēs varētu efektīvāk izmantot un apmainīties ar aprēķina resursiem un matemātiskajām problēmām. Vai varbūt ātrāk risiniet matemātiskos strīdus.

Kudos Ronen Gradwohl, Moni Naor, Benny Pinkas un Gay Rothblum