Tenk deg at du hadde litt nyttig kunnskap - kanskje en hemmelig oppskrift, eller nøkkelen til et chiffer. Kunne du bevise for en venn at du hadde den kunnskapen, uten å avsløre noe om det? Dataforskere beviste for over 30 år siden at du kunne, hvis du brukte det som kalles et null-kunnskapsbevis.
For en enkel måte å forstå denne ideen på, la oss anta at du vil vise vennen din at du vet hvordan du kommer deg gjennom en labyrint, uten å røpe noen detaljer om stien. Du kunne ganske enkelt krysse labyrinten innen en tidsbegrensning, mens vennen din var forbudt å se på. (Tidsgrensen er nødvendig fordi gitt nok tid, kan hvem som helst finne veien ut gjennom prøving og feiling.) Vennen din ville vite at du kunne gjøre det, men de ville ikke vite hvordan.
Nullkunnskapsbevis er nyttig for kryptografer, som jobber med hemmelig informasjon, men også for forskere av beregningsmessig kompleksitet, som omhandler å klassifisere vanskelighetene ved forskjellige problemer. "Mye moderne kryptografi er avhengig av kompleksitetsantakelser - på antagelsen om at visse problemer er vanskelige å løse, så det har alltid vært noen forbindelser mellom de to verdenene," sa Claude Crépeau, en informatiker ved McGill University. "Men [disse] bevisene har skapt en hel verden av forbindelse."
Nullkunnskapsbevis tilhører en kategori kjent som interaktive bevis, så for å lære hvordan førstnevnte fungerer, hjelper det å forstå sistnevnte. Først beskrevet i en artikkel fra 1985 av informatikerne Shafi Goldwasser, Silvio Micali og Charles Rackoff, interaktive bevis fungerer som et avhør: Over en rekke meldinger prøver den ene parten (beviseren) å overbevise den andre (bekrefteren) om at en gitt påstand er sann. Et interaktivt bevis må tilfredsstille to egenskaper. For det første vil en sann uttalelse alltid til slutt overbevise en ærlig verifikatoren. For det andre, hvis det gitte utsagnet er usant, kan ingen bevis - selv en som later til å ha viss kunnskap - overbevise verifikatoren, bortsett fra med ubetydelig liten sannsynlighet.
Interaktive bevis er sannsynlige i naturen. Beviseren kunne svare riktig på ett eller to spørsmål rett og slett ved flaks, så det kreves et stort nok antall utfordringer, som alle må få rett til, for at verifikatoren skal bli trygg på at beviseren faktisk vet at påstanden er sann.
Denne ideen om interaksjoner kom da Micali og Goldwasser – da avgangsstudenter ved University of California, Berkeley – puslet gjennom logistikken ved å spille poker over et nettverk. Hvordan kan alle spillere bekrefte at når en av dem får et kort fra den virtuelle kortstokken, er resultatet tilfeldig? Interaktive bevis kan lede an. Men hvordan kan spillere verifisere at hele protokollen – hele settet med regler – ble fulgt riktig, uten å avsløre hver spillers hånd underveis?
For å oppnå dette målet, la Micali og Goldwasser til en tredje egenskap til de to som trengs for et interaktivt bevis: Beviset skal ikke avsløre noe om kunnskapen i seg selv, bare sannheten til utsagnet. "Det er en forestilling om å gå gjennom en protokoll, på slutten av hvilken du tror at [pokerspillerne] ikke vet noe mer enn det de skal vite," sa Goldwasser.
La oss vurdere det klassiske eksemplet. Alice ønsker å bevise for Bob at en bestemt graf G - en unik samling av hjørner (prikker) forbundet med kanter (linjer) - har en "Hamiltonsk syklus." Dette betyr at grafen har en bane som besøker hver prikk nøyaktig én gang og ender på samme prikk som den startet fra. Alice kunne gjøre dette ved ganske enkelt å vise Bob banen som gjør dette, men da ville han selvfølgelig også kjenne veien.
Her er hvordan Alice kan overbevise Bob om at hun vet at en slik vei eksisterer, uten å vise ham den. Først tegner hun en ny graf, H, det ser ikke ut som G men er lik på en avgjørende måte: Den har samme antall toppunkter, koblet sammen på samme måter. (Hvis G virkelig har en Hamilton-syklus, betyr denne likheten H vil også.) Deretter, etter å ha dekket hver kant inn H med maskeringstape låser hun H i en boks og gir boksen til Bob. Dette hindrer ham i å se det direkte, men hindrer henne også i å endre det. Så tar Bob et valg: Enten kan han be Alice vise det H virkelig ligner på G, eller han kan be henne vise ham Hamiltonian-sykkelen inn H. Begge forespørslene skal være enkle for Alice, forutsatt at det H virkelig ligner nok til G, og at hun virkelig kjenner veien.
Selvfølgelig, selv om Alice ikke kjenner Hamiltonian-syklusen G, kan hun prøve å lure Bob, enten ved å tegne grafer som ikke ligner G, eller ved å sende inn grafer hun ikke kjenner veien til. Men etter at de har spilt flere runder, blir sjansen for at Alice lurer Bob hver gang forsvinnende liten. Hvis hun får alt riktig, vil Bob til slutt være overbevist om at Alice kjenner en Hamilton-syklus i graf G, uten at Bob noen gang har sett det.
Etter den første artikkelen som først beskrev slike bevis, oppdaget Micali og to matematikere - Oded Goldreich og Avi Wigderson - en uventet konsekvens med vidtrekkende effekter. Det har å gjøre med en hovedkategori av problemer med omtrent samme vanskelighetsgrad, kjent som NP. Disse problemene er vanskelige å løse, men løsningene deres er enkle å verifisere. De tre forskerne fant det, hvis virkelig sikker kryptering er mulig, så kan løsningen på ethvert problem i NP også bevises med et nullkunnskapsbevis. Denne studien hjalp forskere tenke på varianter av null-kunnskapsbevis som ikke engang krever sikker kryptering i utgangspunktet; disse er kjent som multi-prover interaktive bevis.
Og i 1988, Micali og andre viste at hvis en beviser og en verifikator deler en kort streng med tilfeldige biter, er ingen interaksjon nødvendig. Dette betydde teoretisk at null-kunnskapsbevis ikke trenger å være interaktive, noe som ville innebære at konstant kommunikasjon mellom to parter ikke er nødvendig. Dette ville gjøre dem mye mer nyttige for forskere, men det var ikke før etter begynnelsen av det 21. århundre at slike bevis tok fart.
"På slutten av 2000-tallet begynte vi å se utviklingen av effektive teknikker for å bygge nullkunnskapsbevis," sa Matthew D. Green, en kryptograf ved John Hopkins University. "Vi kom til det punktet hvor vi innså: 'Vent litt, det kan faktisk være en måte å bruke dette på i praksis.'
Nå kunne en bevisst sende en enkelt melding til en verifikator uten at begge trengte å være online, og forskere kunne lage et veldig kort bevis som raskt kunne verifiseres, selv for svært kompliserte problemer. Dette har ført til flere praktiske bruksområder, for eksempel muligheten til å raskt verifisere blokkjeden etter en kryptovalutatransaksjon samtidig som detaljene i transaksjonen skjules. Og i 2016, en gruppe fysikere viste hvordan bevis med null kunnskap kan hjelpe med atomnedrustning: Uten å avsløre noen hemmelighet om utformingen av dets atomstridshode, kan et land nå bevise overfor atominspektører om stridshodet er aktivt eller inaktivt.
Nylig har fremskritt innen kvanteberegning tvunget Crépeau til å stressteste tidligere forskning for å sikre at nullkunnskapsprotokoller fortsatt er levedyktige. I 2021 hjalp han til demonstrere at multi-prover interaktive bevis beholder hemmeligholdet selv når kvantedatamaskiner er involvert, men å oppnå samme sikkerhetsnivå gjør protokollen mye tregere. Funnet var gode nyheter, sa han, men nye bekymringer vil oppstå etter hvert som teknologien skrider frem.
"Alle typer beregninger vi kan gjøre i fremtiden vil involvere kvantedatamaskiner," sa Crépeau. "Så som gode paranoide kryptografer, når vi vurderer sikkerheten til et system, ønsker vi å sørge for at systemet vårt er trygt."
Redaktørens notat: Shafi Goldwasser har mottatt midler fra Simons Foundation, som også finansierer dette redaksjonell uavhengig publikasjon. Simons Foundations finansieringsbeslutninger har ingen innflytelse på vår dekning.
