Forestil dig, at du havde noget nyttig viden - måske en hemmelig opskrift eller nøglen til en chiffer. Kunne du bevise over for en ven, at du havde den viden, uden at afsløre noget om det? Dataloger beviste for over 30 år siden, at man kunne, hvis man brugte det, der kaldes et nul-vidensbevis.
For en enkel måde at forstå denne idé på, lad os antage, at du vil vise din ven, at du ved, hvordan du kommer gennem en labyrint, uden at afsløre nogen detaljer om stien. Du kunne simpelthen krydse labyrinten inden for en tidsgrænse, mens din ven fik forbud mod at se med. (Tidsgrænsen er nødvendig, fordi givet nok tid, kan enhver i sidste ende finde vej ud gennem forsøg og fejl.) Din ven ville vide, at du kunne gøre det, men de ville ikke vide hvordan.
Nulvidensbeviser er nyttige for kryptografer, der arbejder med hemmelig information, men også for forskere af beregningsmæssig kompleksitet, som beskæftiger sig med at klassificere sværhedsgraden af forskellige problemer. "Meget moderne kryptografi er afhængig af kompleksitetsantagelser - på den antagelse, at visse problemer er svære at løse, så der har altid været nogle forbindelser mellem de to verdener," sagde Claude Crépeau, en datalog ved McGill University. "Men [disse] beviser har skabt en hel verden af forbindelse."
Nulvidensbeviser hører til en kategori kendt som interaktive beviser, så for at lære, hvordan førstnævnte virker, hjælper det at forstå sidstnævnte. Først beskrevet i et papir fra 1985 af datalogerne Shafi Goldwasser, Silvio Micali og Charles Rackoff, interaktive beviser fungerer som et forhør: I løbet af en række meddelelser forsøger den ene part (beviseren) at overbevise den anden (verifikatoren) om, at et givet udsagn er sandt. Et interaktivt bevis skal opfylde to egenskaber. For det første vil et sandt udsagn altid til sidst overbevise en ærlig verifikator. For det andet, hvis den givne udsagn er falsk, kan ingen bevis - selv en, der foregiver at have en vis viden - overbevise verifikatoren, undtagen med ubetydelig lille sandsynlighed.
Interaktive beviser er probabilistiske i naturen. Beviseren kunne svare rigtigt på et eller to spørgsmål blot ved held, så det kræver et stort nok antal udfordringer, som alle skal have ret i, for at verifikatoren kan blive sikker på, at beviseren faktisk ved, at udsagnet er sandt.
Denne idé om interaktioner kom, da Micali og Goldwasser - dengang kandidatstuderende ved University of California, Berkeley - puslede gennem logistikken ved at spille poker over et netværk. Hvordan kan alle spillere bekræfte, at når en af dem får et kort fra det virtuelle spil, er resultatet tilfældigt? Interaktive beviser kunne vise vejen. Men hvordan kan spillere så verificere, at hele protokollen – det fulde sæt af regler – blev fulgt korrekt, uden at afsløre hver spillers hånd undervejs?
For at nå dette mål tilføjede Micali og Goldwasser en tredje egenskab til de to, der var nødvendige for et interaktivt bevis: Beviset skulle ikke afsløre noget om selve viden, kun sandheden af udsagnet. "Der er en idé om at gå igennem en protokol, i slutningen af hvilken du tror, at [pokerspillerne] ikke ved noget mere, end hvad de formodes at vide," sagde Goldwasser.
Lad os overveje det klassiske eksempel. Alice vil bevise for Bob, at en bestemt graf G - en unik samling af hjørner (prikker) forbundet med kanter (linjer) - har en "Hamiltonsk cyklus." Det betyder, at grafen har en sti, der besøger hver prik nøjagtigt én gang og slutter ved den samme prik, som den startede fra. Alice kunne gøre dette ved blot at vise Bob stien, der gør dette, men så ville han selvfølgelig også kende vejen.
Sådan kan Alice overbevise Bob om, at hun ved, at der findes en sådan vej uden at vise ham det. Først tegner hun en ny graf, H, det ser ikke ud til G men ligner på en afgørende måde: Den har det samme antal hjørner, forbundet på samme måder. (Hvis G virkelig har en Hamilton-cyklus, betyder denne lighed H vil også.) Derefter, efter at have dækket hver kant ind H med malertape låser hun H i en kasse og giver kassen til Bob. Dette forhindrer ham i at se det direkte, men forhindrer hende også i at ændre det. Så træffer Bob et valg: Enten kan han bede Alice om at vise det H virkelig ligner G, eller han kan bede hende om at vise ham Hamilton-cyklen ind H. Begge anmodninger burde være nemme for Alice, forudsat at det H virkelig ligner nok G, og at hun virkelig kender vejen.
Selvfølgelig, selvom Alice ikke kender Hamilton-cyklen ind G, kan hun forsøge at narre Bob, enten ved at tegne grafer, der ikke ligner G, eller ved at indsende grafer hun ikke kender vejen til. Men efter at de har spillet flere runder, bliver chancen for at Alice bedrager Bob hver gang forsvindende lille. Hvis hun får alt rigtigt, vil Bob til sidst være overbevist om, at Alice kender en Hamilton-cyklus i graf Guden at Bob nogensinde har set det.
Efter det første papir, der først beskrev sådanne beviser, opdagede Micali og to matematikere - Oded Goldreich og Avi Wigderson - en uventet konsekvens med vidtrækkende virkninger. Det har at gøre med en større kategori af problemer af nogenlunde lige sværhedsgrad, kendt som NP. Disse problemer er svære at løse, men deres løsninger er nemme at verificere. De tre forskere fandt det, hvis virkelig sikker kryptering er muligt, så kan løsningen på ethvert problem i NP også bevises med et nul-viden bevis. Denne undersøgelse hjalp forskere forestille sig varianter af nul-viden beviser, der ikke engang kræver sikker kryptering i første omgang; disse er kendt som multi-prover interaktive beviser.
Og i 1988, Micali og andre viste at hvis en beviser og en verifikator deler en kort streng af tilfældige bits, er ingen interaktion nødvendig. Dette betød teoretisk, at nul-viden beviser ikke behøver at være interaktive, hvilket ville indebære, at konstant kommunikation mellem to parter ikke er nødvendig. Dette ville gøre dem meget mere nyttige for forskere, men det var først efter begyndelsen af det 21. århundrede, at sådanne beviser tog fart.
"I slutningen af 2000'erne begyndte vi at se udviklingen af effektive teknikker til at bygge nul-viden beviser," sagde Matthew D. Green, en kryptograf ved John Hopkins University. "Vi nåede til det punkt, hvor vi indså, 'Vent et øjeblik, der kan faktisk være en måde at bruge dette på i praksis'."
Nu kunne en bevisfører sende en enkelt besked til en verifikator, uden at de begge behøvede at være online, og forskere kunne lave et meget kort bevis, der hurtigt kunne verificeres, selv for meget komplicerede problemer. Dette har ført til flere praktiske anvendelser, såsom muligheden for hurtigt at verificere blockchainen efter en kryptovaluta-transaktion, mens detaljerne i transaktionen skjules. Og i 2016, en gruppe fysikere viste hvordan nul-viden beviser kan hjælpe med atomnedrustning: Uden at afsløre nogen hemmelighed om designet af dets atomsprænghoved, kunne et land nu bevise over for atominspektører, om sprænghovedet er aktivt eller inaktivt.
For nylig har fremskridt inden for kvantecomputere tvunget Crépeau til at stressteste tidligere forskning for at sikre, at nul-viden-protokoller stadig er levedygtige. I 2021 hjalp han til demonstrere at interaktive beviser med flere beviser bevarer deres hemmeligholdelse, selv når kvantecomputere er involveret, men at opnå det samme sikkerhedsniveau gør protokollen meget langsommere. Fundet var gode nyheder, sagde han, men nye bekymringer vil opstå, efterhånden som teknologien udvikler sig.
"Enhver form for beregning, vi kan gøre i fremtiden, vil involvere kvantecomputere," sagde Crépeau. "Så som gode paranoide kryptografer, når vi vurderer sikkerheden af et system, vil vi gerne sikre os, at vores system er sikkert."
Redaktørens note: Shafi Goldwasser har modtaget støtte fra Simons Fonden, som også finansierer dette redaktionelt uafhængig udgivelse. Simons Fondens finansieringsbeslutninger har ingen indflydelse på vores dækning.
