Vidensløst bevis

Vidensløse beviser (eng. zero-knowledge proofs) er en særlig disciplin inden for kryptologien, der tillader en part A at bevise over for en part B, at en (ofte matematisk) sætning er sand, uden at afsløre andet end denne sandhed.

En analogi i virkelighedens verden ville f.eks. være, at en person kunne bevise, at han vidste, hvem der myrdede John F. Kennedy uden at afsløre, hvem morderen var.

For at et vidensløst bevis kan anses for gyldigt skal følgende tre betingelser være opfyldt:

• Komplethed: Er sætningen sand, skal en ærlig modtager acceptere svaret fra den ærlige afsender.
• Sikkerhed: Er sætningen falsk, skal en ærlig modtager ikke acceptere noget som helst bevis for, at den er sand, fra en uærlig afsender – udover med meget en lille sandsynlighed.
• Vidensløst: Er sætningen sand, kan ingen uærlig modtager lære noget som helst herom ud fra beviset af sætningen modtaget fra den ærlige afsender.

De første to sætninger er generelle for alle interaktive bevissystemer, mens det tredje er hvad der adskiller vidensløse beviser fra andre beviser.

En mulig anvendelse af vidensløse beviser er identifikation. Den hemmelige viden kunne virke som en adgangskode. A skal da overbevise B om, at han kender adgangskoden uden at afsløre, hvad adgangskoden er. Dette kaldes "vidensløst bevis for viden".

Et vidensløst bevis er ikke et (gyldigt) matematisk bevis, der da kun sikrer inden for en vis margin, som det vil ses i nedenstående eksempler. Formålet er blot at minimere sandsynligheden for, at en part udgiver sig for at være en anden – muligheden kan aldrig helt afvises. Men hvis man tager et scenarie, hvor angribere har 50% sandsynlighed for at gætte rigtigt, og man gentager dette scenarie 100 gange, så er sandsynligheden for at angriberen kan gætte rigtigt hver gang nede på 2^-100 (altså 7,8 * 10^-31) hvilket er "godt nok" til de fleste praktiske anvendelser, men matematisk stadig er usikkert.

Vidensløse beviser blev første gang introduceret i en artikel af Shafi Goldwasser, Silvio Micali og Charles Rackoff . Oded Goldreich, Silvio Micali og Avi Widgerson viste vidensløse bevisers anvendelse indenfor sikker distribueret beregning.. Deres potentiale blev dog først for alvor vist i en artikel af Goldreich, Micali og Widgerson.

Hule-analogi

Der er en velkendt historie, der forklarer nogle af principperne i vidensløser beviser, som først gang blev publiceret af Jean-Jacques Quisquater og andre i deres "Forklar vidensløser beviser til børn" ("How to Explain Zero-Knowledge Protocols to Your Children"). Det er sædvanlig praksis at navngive de to parter i et (vidensløst) interaktivt bevis som Peggy og Victor, Peggy er den bevisførende og Victor er den verificerende.

I denne historie kender Peggy et hemmeligt kodeord som åbner en dør i en hule. Hulen er formet som en cirkel, med indgangen i den ene ende og den magiske dør blokerende hulen i den anden. Victor vil gerne købe det hemmelige kodeord af Peggy, men ikke før han er sikker på, at hun rent faktisk kender det. Peggy vil ikke fortælle Victor kodeordet, før hun har modtaget pengene. De laver derfor et system, hvor Peggy kan bevise at hun har kodeordet uden at fortælle det. Først derefter skal Victor skal betale Peggy, hvorefter Peggy så fortæller Victor kodeordet.

Først venter Victor uden for hulen, mens Peggy går ind. Vi navngiver de to stier fra indgange A og B for venstre henholdsvist højre. Hun tager tilfældigt indgang A eller B. Efter hun er gået ind af den ene indgang og står i den anden ende af hulen, går Victor ind. Han råber derefter navnet på den indgang, som Peggy skal komme ud af – enten A eller B helt tilfældigt valgt. Victor ved ikke hvilken sti, Peggy er gået ned af. Hvis Peggy er gået ned af sti A, og Victor råber A, så kan hun blot gå tilbage igen. Men hvis Victor råber B, så siger hun blot det hemmelige kodeord, går igennem døren og kommer ud af sti B. Tilsvarende, hvis hun var gået ind af B, kunne hun komme ud af begge stier. Derefter går Victor ud igen, Peggy vælger en sti, Victor kommer ind igen og råber navnet på den sti, hun skal komme ud af.

Hvis hun ikke kendte kodeordet, så kunne hun kun (i gennemsnit) hver anden gang komme ud af den sti, som Victor råbte. Hun kunne selvfølgelig være heldig, at hun valgte samme sti, som Victor tilfældigt råbte, og at hun gjorde dette flere gang i træk, men hvis de gentog dette for eksempel 20 gange, så er sandsynligheden for, at hun gætter det samme, som Victor tilfældigt vælger meget lille. For kun hvis hun hver gang kommer ud af den sti, som Victor råber, kan Victor stole på, at hun kender kodeordet. Laver hun bare en fejl, så kan han ikke stole på hende.

Man kan undres over, hvorfor de ikke bare begge to går ind i hulen, Peggy går ind af sti A og kommer ud af sti B, mens Victor venter ved indgang og kan se det – det ville jo bevise, at hun kunne komme igennem. Men det åbner en mulighed for "aflytning". Victor må jo ikke vide kodeordet, før han har betalt, så ved at vælge en tilfældig sti, kan Peggy sikre sig, at Victor ikke kan liste efter hende og aflytte kodeordet mens hun siger det. At hun vælger en tilfældig sti gør, at afsløringen af informationer er holdt til et minimum.

NP-komplethed og vidensløse beviser

En mulig implementering 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 graf. Og derudover bruges Peggy som den bevisførende afsender, og Victor som den verificerende modtager. Og senere bliver 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 offentliggjort. 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.

Resten mangler fra enwiki – se dog diskussion for at få det formuleret bedre.

Kilde

• Douglas R. Stinson: Cryptography – Theory and Practice. CRC Press, 1995. ISBN 0-8493-8521-0.