Stel je voor dat je wat nuttige kennis had - misschien een geheim recept, of de sleutel tot een cijfer. Zou je een vriend kunnen bewijzen dat je die kennis had, zonder er iets over te onthullen? Computerwetenschappers hebben meer dan 30 jaar geleden bewezen dat je dat zou kunnen, als je een zogenaamd nul-kennisbewijs zou gebruiken.
Voor een eenvoudige manier om dit idee te begrijpen, laten we aannemen dat je je vriend wilt laten zien dat je weet hoe je door een doolhof moet komen, zonder details over het pad te onthullen. Je kon gewoon binnen een tijdslimiet het doolhof doorkruisen, terwijl je vriend niet mocht kijken. (De tijdslimiet is noodzakelijk omdat iedereen, als er genoeg tijd is, uiteindelijk met vallen en opstaan een weg naar buiten kan vinden.) Je vriend zou weten dat je het zou kunnen doen, maar ze zouden niet weten hoe.
Nul-kennisbewijzen zijn nuttig voor cryptografen, die met geheime informatie werken, maar ook voor onderzoekers van computationele complexiteit, die zich bezighouden met het classificeren van de moeilijkheidsgraad van verschillende problemen. "Veel moderne cryptografie is gebaseerd op complexiteitsaannames - in de veronderstelling dat bepaalde problemen moeilijk op te lossen zijn, dus er zijn altijd verbindingen tussen de twee werelden geweest," zei Claude Crepeau, een computerwetenschapper aan de McGill University. "Maar [deze] bewijzen hebben een hele wereld van verbinding gecreëerd."
Nul-kennisbewijzen behoren tot een categorie die bekend staat als interactieve bewijzen, dus om te leren hoe de eerste werken, helpt het om de laatste te begrijpen. Eerst beschreven in een paper uit 1985 van de computerwetenschappers Shafi Goldwasser, Silvio Micali en Charles Rackoff, werken interactieve bewijzen als een ondervraging: via een reeks berichten probeert de ene partij (de bewijzer) de andere (de verificateur) ervan te overtuigen dat een bepaalde bewering waar is. Een interactief bewijs moet aan twee eigenschappen voldoen. Ten eerste zal een waarheidsgetrouwe verklaring uiteindelijk altijd een eerlijke verificateur overtuigen. Ten tweede, als de gegeven bewering onwaar is, kan geen enkele bewijzer - zelfs niet iemand die beweert over bepaalde kennis te beschikken - de verificateur overtuigen, behalve met een verwaarloosbaar kleine waarschijnlijkheid.
Interactieve bewijzen zijn probabilistisch van aard. De bewijzer kan een of twee vragen juist beantwoorden door simpelweg geluk te hebben, dus er zijn een groot genoeg aantal uitdagingen nodig, die de bewijzer allemaal goed moet krijgen, voordat de verificateur er zeker van is dat de bewijzer inderdaad weet dat de bewering waar is.
Dit idee van interacties ontstond toen Micali en Goldwasser - toen afgestudeerde studenten aan de University of California, Berkeley - zich door de logistiek van het spelen van poker via een netwerk verwarden. Hoe kunnen alle spelers verifiëren dat wanneer een van hen een kaart van de virtuele stapel krijgt, het resultaat willekeurig is? Interactieve bewijzen zouden het voortouw kunnen nemen. Maar hoe kunnen spelers dan verifiëren dat het hele protocol - de volledige set regels - correct is gevolgd, zonder de hand van elke speler te onthullen?
Om dit doel te bereiken, voegden Micali en Goldwasser een derde eigenschap toe aan de twee die nodig zijn voor een interactief bewijs: het bewijs mag niets onthullen over de kennis zelf, alleen de waarheid van de verklaring. "Er is een idee van het doorlopen van een protocol, aan het einde waarvan je denkt dat [de pokerspelers] niet meer weten dan wat ze zouden moeten weten," zei Goldwasser.
Laten we eens kijken naar het klassieke voorbeeld. Alice wil Bob bewijzen dat een bepaalde grafiek G - een unieke verzameling hoekpunten (punten) verbonden door randen (lijnen) - heeft een 'Hamiltoniaanse cyclus'. Dit betekent dat de grafiek een pad heeft dat elke stip precies één keer bezoekt en eindigt bij dezelfde stip waar hij begon. Alice zou dit kunnen doen door Bob het pad te laten zien dat dit doet, maar dan zou hij natuurlijk ook het pad kennen.
Hier is hoe Alice Bob ervan kan overtuigen dat ze weet dat zo'n pad bestaat, zonder het hem te laten zien. Eerst tekent ze een nieuwe grafiek, H, dat ziet er niet uit G maar is op een cruciale manier vergelijkbaar: het heeft hetzelfde aantal hoekpunten, op dezelfde manier verbonden. (Als G heeft echt een Hamiltoniaanse cyclus, deze gelijkenis betekent: H zal dat ook doen.) Dan, na het bedekken van elke rand in H met plakband sluit ze af H in een doos en geeft de doos aan Bob. Dit voorkomt dat hij het direct ziet, maar voorkomt ook dat zij het verandert. Dan maakt Bob een keuze: Of hij kan Alice vragen om dat te laten zien H lijkt echt op G, of hij kan haar vragen hem de Hamiltoniaanse cyclus te laten zien in H. Beide verzoeken zouden voor Alice gemakkelijk moeten zijn, ervan uitgaande dat: H is echt vergelijkbaar genoeg om G, en dat ze het pad echt kent.
Natuurlijk, zelfs als Alice de Hamiltoniaanse cyclus niet kent in G, kan ze proberen Bob voor de gek te houden, hetzij door grafieken te tekenen die niet lijken op G, of door grafieken in te dienen waarvan ze het pad niet kent. Maar nadat ze meerdere rondes hebben gespeeld, wordt de kans dat Alice Bob elke keer bedriegt, verwaarloosbaar klein. Als ze alles goed doet, zal Bob er uiteindelijk van overtuigd zijn dat Alice een Hamiltoniaanse cyclus in de grafiek kent G, zonder dat Bob het ooit gezien heeft.
Na het eerste artikel waarin dergelijke bewijzen voor het eerst werden beschreven, ontdekten Micali en twee wiskundigen - Oded Goldreich en Avi Wigderson - een onverwacht gevolg met verstrekkende gevolgen. Het heeft te maken met een grote categorie problemen van ongeveer gelijke moeilijkheidsgraad, bekend als NP. Deze problemen zijn moeilijk op te lossen, maar hun oplossingen zijn gemakkelijk te verifiëren. De drie onderzoekers gevonden dat, indien echt veilige codering is mogelijk, dan kan de oplossing voor elk probleem in NP ook worden bewezen met een nulkennisbewijs. Deze studie hielp onderzoekers bedenken varianten van zero-knowledge proofs die in de eerste plaats geen veilige codering vereisen; deze staan bekend als multi-prover interactieve bewijzen.
En in 1988, Micali en anderen vertoonde dat als een bewijzer en een verificateur een korte reeks willekeurige bits delen, er geen interactie nodig is. Dit betekende in theorie dat zero-knowledge proofs niet interactief hoeven te zijn, wat zou impliceren dat constante communicatie tussen twee partijen niet nodig is. Dit zou ze veel nuttiger maken voor onderzoekers, maar het was pas na de eeuwwisseling dat dergelijke bewijzen van de grond kwamen.
"Aan het einde van de jaren 2000 begonnen we de evolutie te zien van efficiënte technieken voor het bouwen van zero-knowledge proofs," zei Matthew D. Groen, een cryptograaf aan de John Hopkins University. "We kwamen op het punt dat we ons realiseerden: 'Wacht even, er is misschien een manier om dit in de praktijk te gebruiken.'"
Nu kan een bewijzer een enkel bericht naar een verificateur sturen zonder dat ze allebei online hoeven te zijn, en onderzoekers kunnen een heel kort bewijs maken dat snel kan worden geverifieerd, zelfs voor zeer gecompliceerde problemen. Dit heeft geleid tot verschillende praktische toepassingen, zoals de mogelijkheid om de blockchain snel te verifiëren na een cryptocurrency-transactie terwijl de details van de transactie worden verborgen. En in 2016, een groep natuurkundigen vertoonde hoe zero-knowledge proofs kunnen helpen bij nucleaire ontwapening: Zonder enig geheim te onthullen over het ontwerp van zijn kernkop, zou een land nu aan nucleaire inspecteurs kunnen bewijzen of de kernkop actief of inactief is.
Meer recentelijk hebben vorderingen in kwantumcomputing Crépeau gedwongen om eerder onderzoek te stresstesten om ervoor te zorgen dat nulkennisprotocollen nog steeds levensvatbaar zijn. In 2021 hielp hij tonen dat interactieve bewijzen met meerdere bewijzen hun geheim bewaren, zelfs als er kwantumcomputers bij betrokken zijn, maar het bereiken van hetzelfde beveiligingsniveau maakt het protocol veel langzamer. De bevinding was goed nieuws, zei hij, maar naarmate de technologie vordert, zullen er nieuwe zorgen ontstaan.
"Bij elk type berekening dat we in de toekomst kunnen doen, zullen kwantumcomputers betrokken zijn", zei Crépeau. "Dus als goede paranoïde cryptografen willen we er bij het beoordelen van de beveiliging van een systeem zeker van zijn dat ons systeem veilig is."
Noot van de redactie: Shafi Goldwasser heeft financiering ontvangen van de Simons Foundation, die dit ook financiert redactioneel onafhankelijke publicatie. Financieringsbeslissingen van de Simons Foundation hebben geen invloed op onze dekking.
