CWI researcher designs award-winning cryptographic lottery algorithm

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.

Generating random numbers is a notoriously delicate problem for computers. It becomes even trickier when many parties wish to have a guarantee that nobody can cheat. This problem is similar to national lotteries: a winner has to be chosen at random, and all the participants should be convinced that the selection process is fair, and the lottery ball machine has not been tampered with.

Virtual analogues of lottery machines play an important role in decentralised systems such as cryptocurrencies. In such a context, the number of parties involved can be very large, and reaching consensus on an unbiased random number can be a challenge. A solution was proposed in 2016 by Arjen Lenstra, professor at the École polytechnique fédérale de Lausanne, Switzerland (EPFL) and Benjamin Wesolowski, researcher at CWI. It consists in voluntarily slowing down the process of generating the randomness, thanks to an operation carefully designed to be slow to compute: a 'verifiable delay function', or VDF.

However, no satisfying construction of a VDF was known at the time: even though it should require a lot of time to compute it (and an army of computers should not allow to go faster), anyone should be able to efficiently verify that the result, once known, is correct. That situation changed when two constructions were proposed independently at two days interval: one by Wesolowski, and one by Krzysztof Pietrzak, Professor at IST Austria. Wesolowski's solution was presented at the Eurocrypt 2019 conference, where he received the Best Young Researcher Paper Award for it. Eurocrypt, together with CRYPTO, is the premier cryptography research conference in the world.

This fundamental new construction has sparked interest in the community of blockchain technology, and many platforms have plans to integrate VDFs in their infrastructure. They are notably a key ingredient to design secure blockchain protocols that do not consume colossal amounts of electrical power. The topic generates great interest all over the world. Aiming for greener blockchain technology, Chia Network is organising a competition with more than $100,000 prize money for fast implementation of 'class group arithmetic', one of the two possible foundational structures underlying Wesolowski's VDF construction. Independently, the Ethereum Foundation and Protocol Labs are running a $1,000,000 competition focused on the alternative 'RSA arithmetic'.

Benjamin Wesolowski is a member of the Cryptology research group at CWI, headed by Prof. Ronald Cramer. This group investigates fundamental cryptographic questions from a broad scientific perspective, particularly from mathematics, computer science and physics.