CWI-onderzoeker ontwerpt bekroond algoritme voor cryptografische loterijen

CWI-onderzoeker Benjamin Wesolowski ontwikkelde een nieuw belangrijk ingrediënt voor cryptografische loterijmachines en ontving hiervoor de Best Young Researcher Paper Award tijdens Eurocrypt 2019. Zijn resultaten kunnen worden gebruikt voor duurzamere blockchain technologie.

Het genereren van willekeurige getallen is een berucht gevoelig probleem voor computers. Het wordt nog lastiger als veel partijen de garantie willen hebben dat niemand vals kan spelen. Dit probleem speelt ook bij nationale loterijen: een winnaar moet willekeurig gekozen worden en alle deelnemers moeten ervan overtuigd zijn dat het selectieproces eerlijk is en dat er niet met de ballenmachine van de loterij is geknoeid.

Cryptografieonderzoek

Virtuele analogieën van loterijmachines spelen een belangrijke rol in gedecentraliseerde systemen zoals cryptovaluta. In zo’n context kan het aantal betrokken partijen erg groot zijn en kan het een uitdaging zijn om consensus te bereiken over een volstrekt willekeurig getal. In 2016 werd een oplossing voorgesteld door Arjen Lenstra, hoogleraar aan de École polytechnique fédérale de Lausanne, Zwitserland (EPFL) en CWI-onderzoeker Benjamin Wesolowski. Het bestaat uit het vrijwillig vertragen van het proces om volstrekt willekeurige nummers te genereren, dankzij een operatie die zorgvuldig is ontworpen om alleen langzaam te kunnen worden berekend: een 'verifieerbare vertragingsfunctie' (Engels: verifiable delay function) of VDF.

Destijds was er echter geen bevredigende constructie van een VDF bekend; ook al zou het veel tijd moeten kosten om die te berekenen (een heel leger van computers zou niet sneller mogen gaan), toch zou iedereen efficiënt moeten kunnen controleren of het resultaat correct is. Die situatie veranderde toen onafhankelijk van elkaar, met een tussenpoos van twee dagen, twee constructies werden voorgesteld: één door Wesolowski, en één door Krzysztof Pietrzak, hoogleraar aan IST Austria. Wesolowski's oplossing werd gepresenteerd op de Eurocrypt 2019-conferentie, waar hij er de Best Young Researcher Paper Award voor ontving. Eurocrypt is samen met CRYPTO de belangrijkste conferentie ter wereld voor cryptografieonderzoek.

Energieverbruik

Deze fundamentele nieuwe constructie heeft interesse gewekt in de gemeenschap van blockchaintechnologie en veel platforms hebben plannen om VDFs in hun infrastructuur te integreren. Ze zijn met name een belangrijk ingrediënt voor het ontwerpen van veilige blockchainprotocollen die geen kolossale hoeveelheden stroom verbruiken. Het onderwerp wekt over de hele wereld grote belangstelling. In het streven naar groenere blockchain-technologie organiseert Chia Network een wedstrijd met meer dan 100.000 dollar aan prijzengeld voor de snelle implementatie van 'class group arithmetic', een van de twee mogelijke basisstructuren die ten grondslag liggen aan Wesolowski's VDF-constructie. Onafhankelijk daarvan organiseren de Ethereum Foundation en Protocol Labs een wedstrijd van 1 miljoen dollar, gericht op het alternatieve 'RSA arithmetic'.

Benjamin Wesolowski is lid van de CWI-onderzoeksgroep Cryptology, onder leiding van prof. Ronald Cramer. Deze groep onderzoekt fundamentele cryptografische vragen vanuit een breed wetenschappelijk perspectief, met name wiskunde, informatica en natuurkunde.