Probe de cunoaștere zero explicate Partea a 2-a: Dovezi de interacțiune zero non-interactive

Exemplu de dovezi non-interactive de cunoaștere zero: Sudoku și cărți de joc

În prima parte a seriei noastre de dovezi despre cunoașterea zero, am explicat cum ar putea funcționa o dovadă de cunoaștere zero atunci când verificatorul și proverul interacționează între ei..

O dovadă interactivă de cunoaștere zero are avantajul că numai verificatorul poate fi absolut convins că proverul are cunoștințe. Dar acest lucru poate fi și un dezavantaj.

Dacă participanții și observatorii nu pot verifica cererea, proverbul trebuie să interacționeze cu fiecare verificator în mod independent - ceea ce necesită timp și necesită resurse.

În aceasta, partea a 2-a vom analiza dovezile non-interactive de cunoaștere zero.

Dovezi non-interactive de cunoaștere zero

Motivul pentru dovezile non-interactive de cunoaștere zero este de a permite unui număr mare de observatori să verifice eficient dovada.

Nu întotdeauna trebuie să facem dovezi de cunoaștere zero non-interactive. Destul de des este posibil să găsești un verificator de încredere, care se bucură de integritatea dovezii.

Exemplu de dovezi non-interactive de cunoaștere zero: Sudoku și cărți de joc

Sudoku este un joc cu dificultăți diferite, dar reguli relativ simple. Fiecare dintre cele 9 rânduri, 9 coloane și 9 sectoare (așa cum este indicat de linia neagră groasă) trebuie să conțină fiecare număr de la 1 la 9 exact o dată.

Imaginează-ți că soluția unui puzzle sudoku este deosebit de greu de obținut și durează zile în care chiar și un supercomputer poate calcula.

Dar cineva (proverbul) susține că are soluția puzzle-ului și este dispus să-l vândă la un preț. Cum pot dovedi că au soluția - fără să o dezvăluie -, astfel încât verificatorul este pregătit să efectueze plata?

Dovada:

Proverbul are nevoie de 27 de cărți de joc (din orice costum) cu numărul 1-9-243 în total.

Acum, proverul pune în fiecare cutie trei cărți cu numărul corespunzător soluției corecte de Sudoku. De exemplu, dacă răspunsul corect pentru cutie este 7, proverul va pune 3 cărți de joc cu valoarea de 7 în ea.

Pe o masă sudoku, vor fi vizibile câteva răspunsuri. Pe aceste căsuțe, răspuns, se așează cărțile de joc cu fața în sus. Pe casetele Sudoku, care sunt goale, sunt plasate cărțile Fata in jos.

Pentru a dovedi că cărțile cu fața în jos sunt toate în poziția corectă (fără a dezvălui soluția), proverul trebuie să:

  • Ia cartea de sus din fiecare rând și faceți 9 grămezi
  • Ia cartea de sus din fiecare coloană și faceți 9 grămezi
  • Luați cărțile rămase de la fiecare sector și faceți 9 grămezi

Aplicații pentru dovezi de cunoaștere zero

Fiecare grămadă este apoi amestecată și întoarsă.

Fiecare număr cuprins între 1-9 trebuie să apară în fiecare rând, coloană și sector Sudoku. Așadar, dacă fiecare grămadă de cărți ale proverbei (din rândul, coloana și sectorul) conține fiecare carte de joc în valoare de 1-9, știm că acestea trebuie să aibă soluția.

Aplicații pentru dovezi de cunoaștere zero

Desigur, câmpul relativ tânăr al dovezilor de cunoaștere zero nu a găsit încă acceptarea pe care o poate merita. Cu toate acestea, s-ar putea dovedi a fi extrem de valoroase.

Multe probleme matematice sunt asemănătoare cu un puzzle Sudoku (de exemplu, problema de Colorare a graficii). Dacă putem folosi principiul de mai sus și îl putem aplica cu succes la o varietate de probleme, am putea fi în măsură să folosim și să schimbăm mai eficient resursele de calcul și problemele matematice. Sau poate rezolva mai repede problemele matematice.

Kudos lui Ronen Gradwohl, Moni Naor, Benny Pinkas și Guy Rothblum

Probe de cunoaștere zero explicate Partea a 2-a: Dovezi de interacțiune zero non-interactive
admin Author
Sorry! The Author has not filled his profile.