Hoe wantrouwige partijen veilig kunnen samenwerken
Cryptograaf Max Fillinger ontwikkelde nieuwe methodes om een groep algoritmes genaamd commitment schemes te analyseren. Deze schema’s zijn bouwstenen voor een cryptografisch protocol, dat het mogelijk maakt voor partijen die elkaar niet vertrouwen om toch veilig samen te werken. Op 19 maart verdedigt hij zijn proefschrift.
Informatie veilig houden
Fillinger promoveert bij het Centrum Wiskunde & Informatica (CWI) en het Mathematisch Instituut (MI) in Leiden, en wordt begeleid door Serge Fehr. Met zijn nieuwe analysemethodes bewees Fillinger dat een bestaand relativistic commitment scheme, bedacht in 2015, massaal is onderschat. ‘Voorheen werd aangenomen dat de informatie in dit schema slechts een paar miliseconden veilig was, maar in werkelijkheid blijft het veilig voor nagenoeg onbepaalde tijd – of totdat het geheugen van de apparaten die ermee werken vol is', zegt hij. Dit resultaat toont het nut aan van zijn nieuw ontwikkelde methoden voor het analyseren van commitment schemes.
Wat is een commitment scheme?
Laten we het uitzoeken! Stel je de volgende situatie voor: Alice heeft een prognose gemaakt van de beurs. Ze wil Bob overtuigen van haar vermogen om te voorspellen, maar ze wil hem geen gratis advies geven. Daarom wil ze haar voorspelling eerst geheim houden. Maar als ze pas haar voorspelling onthult nadat deze uitkomt, zal Bob niet geloven dat ze de beurs juist heeft voorspeld. Dus geeft ze haar voorspelling aan Bob in een gesloten kluis. Pas nadat de voorspelling uitkomt, geeft ze hem de sleutel. Op deze manier weet Bob dat de voorspelling juist was, en hoeft Alice geen gratis advies weg te geven. Commitment schemes implementeren deze functionaliteit door middel van digitale communicatie en berekeningen, in plaats van een kluis.
Beveiliging gegarandeerd
De meeste commitment schemes die in de praktijk worden gebruikt, zijn computationeel veilig, zoals bij de cryptomunt Zerocoin. Dit betekent dat het met de huidige computers jaren of tientallen jaren zou kosten om de code te kraken, oftewel om vals te spelen. ‘Maar theoretisch is er ook het begrip van onvoorwaardelijke beveiliging’, zegt Fillinger. 'Hier moet de kans op onopgemerkt valsspelen minuscuul blijven, ongeacht de computationele kracht die de valsspeler tot zijn beschikking heeft.' Dat klinkt ideaal, maar het is al wiskundig bewezen dat onvoorwaardelijk beveiligde commitment schemes met één computer onmogelijk zijn.
Sneller dan het licht?
Toch is er goed nieuws: wetenschappers hebben een ander schema gevonden dat onvoorwaardelijk is. In 1988 stelde een groep onderzoekers een commitment scheme voor waarbij Alice (uit het voorbeeld in de kader) twee computers zou gebruiken. 'Eén computer creëert de voorspelling van Alice, de andere opent het', zegt Fillinger. 'Als de computers geen informatie kunnen uitwisselen, wordt het voor Alice onmogelijk om vals te spelen.' Maar als Bob Alice niet vertrouwt, hoe kan hij dan zeker zijn dat ze niet vals speelt door informatie van de ene computer naar de andere te sturen? 'Omdat informatie niet sneller kan reizen dan licht, is er een kort tijdsbestek waar het fysiek onmogelijk is voor de computers om informatie uit te wisselen', zegt de cryptograaf. 'Tijdens dit extreem korte tijdsbestek is de commitment onvoorwaardelijk veilig!'
De som der delen
Adrian Kent breidde dit idee vanaf 1999 uit en introduceerde het concept van relativistic commitment schemes: deze schema's blijven voor onbepaalde tijd onvoorwaardelijk veilig, maar de computer van Bob moet voortdurend berichten uitwisselen met Alice's computers op precieze tijdstippen. 'Eerder werden relativistic commitment schemes als een geheel geanalyseerd. Dit zorgt voor een aantal moeilijk leesbare bewijzen.’ Fillinger biedt in zijn proefschrift een meer modulaire aanpak door delen van het schema afzonderlijk te analyseren. 'Ter toelichting: als de afzonderlijke delen van een relativistic commitment scheme veilig zijn, volgt wiskundig gezien de beveiliging van het geheel. Dit maakt het eenvoudiger om deze schema's te analyseren.'