Nullkunnskapsprøve forklart Del 2: Ikke-interaktive bevis på null kunnskap

[ware_item id=33][/ware_item]

Ikke-interaktive eksempler på null kunnskap, Sudoku og spillkort


I del 1 av serien vår med null kunnskap, forklarte vi hvordan et bevis på null kunnskap kunne fungere når verifikatoren og prover samhandler med hverandre.

Et interaktivt null-kunnskaps bevis har fordelen at bare verifisereren kan være helt overbevist om at den prover har kunnskapen. Men dette kan også være en ulempe.

Hvis tilskuere og observatører ikke kan bekrefte påstanden, må prover deretter samhandle med hver verifiserer uavhengig - noe som tar tid og er ressurskrevende.

I dette, del 2, skal vi se på ikke-interaktive bevis på null kunnskap.

Ikke-interaktive bevis på null kunnskap

Årsaken til ikke-interaktive bevis på null kunnskap er å la et stort antall observatører verifisere beviset effektivt.

Vi trenger ikke alltid å lage bevis som ikke har kunnskap, som ikke er interaktive. Ofte er det mulig å finne en pålitelig verifikator, som garanterer seg bevisets integritet.

Ikke-interaktive eksempler på null kunnskap, Sudoku og spillkort

Sudoku er et spill med ulik vanskelighetsgrad, men relativt enkle regler. Hver av de 9 radene, 9 kolonnene og 9 sektorene (som indikert av den tykke, svarte linjen) må inneholde hvert tall fra 1 til 9 nøyaktig en gang.

Se for deg at løsningen på et sudoku-puslespill er spesielt vanskelig å få tak i, og det tar flere dager før en super datamaskin kan beregne.

Men noen (den prover) hevder å ha løsningen på puslespillet og er villig til å selge det for en pris. Hvordan kan de bevise at de har løsningen - uten å avsløre den - slik at verifisereren er villig til å betale?

Beviset:

Proveren trenger 27 spillkort (av hvilken som helst farge) nummerert 1-9—243 totalt.

Nå setter proveren tre kort med nummeret som tilsvarer riktig Sudoku-løsning i hver boks. E.G., hvis riktig svar for boksen er 7, vil prover sette 3 spillkort med verdien 7 i den.

På et Sudoku-bord vil noen svar være synlige. På disse, besvarte boksene, er spillkortene plassert med ansiktet opp. På Sudoku-boksene som er tomme, plasseres kortene med forsiden ned.

For å bevise at frontkortene alle er i riktig posisjon (uten å avsløre løsningen), må prover:

  • Ta det øverste kortet fra alle rad og lag 9 hauger
  • Ta det øverste kortet fra alle kolonne og lag 9 hauger
  • Ta de resterende kortene fra alle sektor og lag 9 hauger

Søknader om null kunnskap

Hver bunke blir deretter blandet og snudd.

Hvert nummer mellom 1-9 må vises i hver Sudoku-rad, kolonne og sektor. Så hvis hver bunke av proverens kort (fra rad-, kolonne- og sektorhauger) inneholder hvert spillkort som er verdsatt 1-9, vet vi at de må ha løsningen.

Søknader om null kunnskap

Riktignok har det relativt unge feltet med null-kunnskapsbevis ennå ikke funnet aksepten som det kan fortjene. De kan imidlertid vise seg å være svært verdifulle.

Mange matematiske problemer ligner på et Sudoku-puslespill (for eksempel problemet med grafikkfarging). Hvis vi kan bruke ovennevnte prinsipp og lykkes med å bruke det på en rekke problemer, kan vi kanskje bruke og bytte beregningsressurser og matematiske problemer mer effektivt. Eller kanskje løse matematiske kvartaler raskere.

Kudos til Ronen Gradwohl, Moni Naor, Benny Pinkas, og Guy Rothblum

Nullkunnskapsprøve forklart Del 2: Ikke-interaktive bevis på null kunnskap
admin Author
Sorry! The Author has not filled his profile.