Nul-kennisproeven uitgelegd Deel 2: Niet-interactieve nul-kennisproeven

[ware_item id=33][/ware_item]

Voorbeeld van niet-interactieve nulkennisproeven: Sudoku en speelkaarten


In deel 1 van onze zero-knowledge proof-serie, legden we uit hoe een zero-knowledge proof zou kunnen werken wanneer de verifier en de spreekwoord met elkaar communiceren.

Een interactief nulkennisbewijs heeft het voordeel dat alleen de verificateur absoluut overtuigd kan worden dat de spreekbuis de kennis heeft. Maar dit kan ook een nadeel zijn.

Als omstanders en waarnemers de claim niet kunnen verifiëren, moet de spreker vervolgens onafhankelijk met elke verificateur communiceren - wat tijd kost en veel middelen vereist.

In dit deel 2 zullen we kijken naar niet-interactieve zero-knowledge bewijzen.

Niet-interactieve zero-knowledge bewijzen

De reden voor niet-interactieve nulkennisproeven is om een ​​groot aantal waarnemers in staat te stellen het bewijs efficiënt te verifiëren.

We hoeven niet altijd nulkennisbewijzen niet-interactief te maken. Vaak is het mogelijk om een ​​vertrouwde verificateur te vinden, die instaat voor de integriteit van het bewijs.

Voorbeeld van niet-interactieve nulkennisproeven: Sudoku en speelkaarten

Sudoku is een spel met verschillende moeilijkheidsgraden maar relatief eenvoudige regels. Elk van de 9 rijen, 9 kolommen en 9 sectoren (zoals aangegeven door de dikke zwarte lijn) moet elk nummer van 1 tot 9 precies één keer bevatten.

Stel je voor dat de oplossing voor een sudoku-puzzel bijzonder moeilijk te verkrijgen is en dat het dagen duurt voordat zelfs een supercomputer is berekend.

Maar iemand (de spreekwoord) beweert de oplossing voor de puzzel te hebben en is bereid deze voor een prijs te verkopen. Hoe kunnen ze bewijzen dat ze de oplossing hebben - zonder deze te onthullen - zodat de verificateur bereid is om de betaling te verrichten?

Het bewijs:

De prover heeft in totaal 27 speelkaarten (van welke kleur dan ook) genummerd 1-9 - 243.

Nu plaatst de prover drie kaarten met het nummer dat overeenkomt met de juiste Sudoku-oplossing in elk vak. E.G., als het juiste antwoord voor het vak 7 is, plaatst de speler 3 speelkaarten met de waarde 7 erin.

Op een Sudoku-tafel zijn enkele antwoorden zichtbaar. Op deze beantwoorde dozen worden de speelkaarten geplaatst gezicht omhoog. Op de lege Sudoku-dozen worden de kaarten geplaatst gezicht naar beneden.

Om te bewijzen dat de kaarten met de afbeelding naar beneden liggen (zonder de oplossing te onthullen), moet de spreekwoord:

  • Pak de bovenste kaart van elke rij en maak 9 stapels
  • Pak de bovenste kaart van elke kolom en maak 9 stapels
  • Neem de resterende kaarten van elke sector en maak 9 stapels

Toepassingen voor nulkennisbewijzen

Elke stapel wordt vervolgens geschud en omgedraaid.

Elk getal tussen 1-9 moet in elke Sudoku-rij, kolom en sector worden weergegeven. Dus als elke stapel kaarten van de speler (uit de rij-, kolom- en sectorstapels) elke speelkaart met de waarde 1-9 bevat, weten we dat ze de oplossing moeten hebben.

Toepassingen voor nulkennisbewijzen

Toegegeven, het relatief jonge veld van nulkennisbewijzen heeft nog niet de acceptatie gevonden die het verdient. Ze kunnen echter zeer waardevol blijken te zijn.

Veel wiskundige problemen zijn vergelijkbaar met een Sudoku-puzzel (bijvoorbeeld het probleem met Graph Coloring). Als we het bovenstaande principe kunnen gebruiken en met succes kunnen toepassen op een verscheidenheid aan problemen, kunnen we computationele bronnen en wiskundige problemen mogelijk efficiënter gebruiken en verhandelen. Of misschien wiskundige problemen sneller oplossen.

Een pluim voor Ronen Gradwohl, Moni Naor, Benny Pinkas en Guy Rothblum

Nul-kennisproeven uitgelegd Deel 2: Niet-interactieve nul-kennisproeven
admin Author
Sorry! The Author has not filled his profile.