Föreställ dig att du hade lite användbar kunskap - kanske ett hemligt recept eller nyckeln till ett chiffer. Skulle du kunna bevisa för en vän att du hade den kunskapen, utan att avslöja något om det? Datavetare bevisade för över 30 år sedan att du kunde, om du använde det som kallas ett noll-kunskapsbevis.
För ett enkelt sätt att förstå denna idé, låt oss anta att du vill visa din vän att du vet hur man tar sig igenom en labyrint, utan att avslöja några detaljer om vägen. Du kunde helt enkelt korsa labyrinten inom en tidsgräns, medan din vän förbjöds att titta. (Tidsgränsen är nödvändig eftersom med tillräckligt med tid kan vem som helst hitta sin väg ut genom försök och misstag.) Din vän skulle veta att du kunde göra det, men de skulle inte veta hur.
Noll-kunskapsbevis är till hjälp för kryptografer, som arbetar med hemlig information, men också för forskare av beräkningskomplexitet, som handlar om att klassificera svårigheten för olika problem. "Mycket modern kryptografi bygger på komplexitetsantaganden - på antagandet att vissa problem är svåra att lösa, så det har alltid funnits några kopplingar mellan de två världarna," sa Claude Crépeau, en datavetare vid McGill University. "Men [dessa] bevis har skapat en hel värld av anslutning."
Noll-kunskapsbevis tillhör en kategori som kallas interaktiva bevis, så för att lära sig hur de förra fungerar, hjälper det att förstå de senare. Först beskriven i en artikel från 1985 av datavetarna Shafi Goldwasser, Silvio Micali och Charles Rackoff, interaktiva bevis fungerar som ett förhör: Under en rad meddelanden försöker den ena parten (bevisaren) övertyga den andra (verifieraren) om att ett givet påstående är sant. Ett interaktivt bevis måste uppfylla två egenskaper. För det första kommer ett sant uttalande alltid så småningom att övertyga en ärlig verifierare. För det andra, om det givna påståendet är falskt, kan ingen bevisare – inte ens en som låtsas ha viss kunskap – övertyga verifieraren, förutom med försumbar liten sannolikhet.
Interaktiva bevis är probabilistiska till sin natur. Bevisaren kunde svara rätt på en eller två frågor helt enkelt av tur, så det krävs ett tillräckligt stort antal utmaningar, som alla måste lösa, för att verifieraren ska bli säker på att bevisaren faktiskt vet att påståendet är sant.
Denna idé om interaktion kom när Micali och Goldwasser – då doktorander vid University of California, Berkeley – funderade över logistiken med att spela poker över ett nätverk. Hur kan alla spelare verifiera att resultatet är slumpmässigt när en av dem får ett kort från den virtuella kortleken? Interaktiva bevis kan leda vägen. Men hur kan spelare sedan verifiera att hela protokollet – hela uppsättningen regler – följdes korrekt, utan att avslöja varje spelares hand på vägen?
För att uppnå detta mål lade Micali och Goldwasser till en tredje egenskap till de två som behövs för ett interaktivt bevis: Beviset ska inte avslöja något om själva kunskapen, bara sanningshalten i påståendet. "Det finns en idé om att gå igenom ett protokoll, i slutet av vilket du tror att [pokerspelarna] inte vet något mer än vad de ska veta," sa Goldwasser.
Låt oss överväga det klassiska exemplet. Alice vill bevisa för Bob att en viss graf G — en unik samling av hörn (punkter) förbundna med kanter (linjer) — har en "Hamiltonsk cykel." Det betyder att grafen har en sökväg som besöker varje punkt exakt en gång och slutar på samma punkt som den började från. Alice skulle kunna göra detta genom att helt enkelt visa Bob vägen som gör detta, men då skulle han förstås också veta vägen.
Så här kan Alice övertyga Bob om att hon vet att det finns en sådan väg, utan att visa den för honom. Först ritar hon en ny graf, H, det ser inte ut som G men liknar på ett avgörande sätt: Den har samma antal hörn, sammankopplade på samma sätt. (Om G verkligen har en Hamiltonsk cykel, betyder denna likhet H kommer också.) Sedan, efter att ha täckt varje kant in H med maskeringstejp låser hon H i en låda och ger lådan till Bob. Detta hindrar honom från att se det direkt men hindrar henne också från att ändra det. Sedan gör Bob ett val: Antingen kan han be Alice att visa det H verkligen liknar G, eller så kan han be henne visa honom Hamiltons cykel in H. Båda förfrågningarna borde vara lätta för Alice, förutsatt att H verkligen är tillräckligt lik G, och att hon verkligen känner till vägen.
Naturligtvis, även om Alice inte känner till Hamiltons cykel in G, hon kan försöka lura Bob, antingen genom att rita grafer som inte liknar G, eller genom att skicka in grafer hon inte vet vägen till. Men efter att de har spelat flera omgångar blir chansen för att Alice ska lura Bob varje gång försvinnande liten. Om hon får allt rätt kommer Bob så småningom att bli övertygad om att Alice kan en Hamiltonsk cykel i grafen G, utan att Bob någonsin har sett den.
Efter den första uppsatsen som först beskrev sådana bevis upptäckte Micali och två matematiker - Oded Goldreich och Avi Wigderson - en oväntad konsekvens med långtgående effekter. Det har att göra med en större kategori av problem av ungefär lika svårighetsgrad, känd som NP. Dessa problem är svåra att lösa, men deras lösningar är lätta att verifiera. De tre forskarna hittade det, om verkligen säker kryptering är möjligt, då kan lösningen på varje problem i NP också bevisas med ett noll-kunskapsbevis. Denna studie hjälpte forskare tänka sig varianter av nollkunskapsbevis som inte ens kräver säker kryptering i första hand; dessa är kända som multi-prover interaktiva bevis.
Och 1988, Micali och andra visade att om en provare och en verifierare delar en kort sträng av slumpmässiga bitar, är ingen interaktion nödvändig. Detta innebar teoretiskt att nollkunskapsbevis inte behöver vara interaktiva, vilket skulle innebära att konstant kommunikation mellan två parter inte är nödvändig. Detta skulle göra dem mycket mer användbara för forskare, men det var inte förrän efter 21-talets början som sådana bevis tog fart.
"I slutet av 2000-talet började vi se utvecklingen av effektiva tekniker för att bygga nollkunskapsbevis," sa Matthew D. Green, en kryptograf vid John Hopkins University. "Vi kom till den punkt där vi insåg, 'vänta lite, det kan faktiskt finnas ett sätt att använda detta i praktiken'."
Nu kunde en provare skicka ett enda meddelande till en verifierare utan att båda behövde vara online, och forskare kunde skapa ett mycket kort bevis som snabbt kunde verifieras, även för mycket komplicerade problem. Detta har lett till flera praktiska användningsområden, såsom möjligheten att snabbt verifiera blockkedjan efter en kryptovalutatransaktion samtidigt som detaljerna i transaktionen döljs. Och 2016, en grupp fysiker visade hur noll-kunskapsbevis kan hjälpa till med kärnvapennedrustning: Utan att avslöja någon hemlighet om utformningen av dess kärnvapenstridsspets kan ett land nu bevisa för kärnkraftsinspektörer om stridsspetsen är aktiv eller inaktiv.
På senare tid har framsteg inom kvantberäkningen tvingat Crépeau att stresstesta tidigare forskning för att säkerställa att nollkunskapsprotokoll fortfarande är genomförbara. 2021 hjälpte han till demonstrera att interaktiva bevis för flera prover behåller sin sekretess även när kvantdatorer är inblandade, men att uppnå samma säkerhetsnivå gör protokollet mycket långsammare. Fyndet var goda nyheter, sa han, men nya farhågor kommer att uppstå när tekniken går framåt.
"Varje typ av beräkning vi kan göra i framtiden kommer att involvera kvantdatorer," sa Crépeau. "Så som bra paranoida kryptografer, när vi bedömer säkerheten i ett system, vill vi se till att vårt system är säkert."
Redaktörens anmärkning: Shafi Goldwasser har fått medel från Simons Foundation, som också finansierar detta redaktionellt oberoende publikation. Simons Foundations finansieringsbeslut har inget inflytande på vår täckning.
