Vidensløst bevis: Forskelle mellem versioner
Content deleted Content added
Nutids-"r" |
Manscher (diskussion | bidrag) |
||
Linje 41:
== NP-komplethed og vidensløse beviser ==
En mulig implementation af vidensløse beviser, der overholder de tre ovenstående betingelser, er at bruge et [[NP-komplet]] problem, som den viden, som både (den ærlige) afsender og (den ærlige) modtager har. Til eksemplet herunder bruges problemet om en [[hamiltonkreds]], som skal findes i en given [[Grafteori|graf]]. Og derudover bruges [[Alice og Bob|Peggy]] som den bevisførende afsender, og [[Alice og Bob|Victor]] som den verificerende modtager. Og senere bliver [[Alice og Bob|Mallory]] introduceret som en aktiv angriber, der forsøger at snyde Victor.
Peggy kender en graf, ''G'', hvor alle noder er navngivne, og som Peggy har offentligt gjort. Altså alle kan spørge Peggy om hendes offentlige graf, og de får ''G'' returneret. I ''G'' kender Peggy en [[hamiltonkreds]]. Kun Peggy kender denne hamiltonkreds (hun kan for eksempel selv have lavet hele ''G'' ud fra, at der skal være en bestemt hamiltonkreds i den), og da problemet med at finde en hamiltonkreds i en given graf er [[NP-komplet]], kan det anses for usandsynligt, at en anden part (fx Mallory), kan finde denne kreds inden for en sandsynlig tidsperiode.
| |||