Self-taught programmer solved a cryptographic puzzle that lasted 20 years

Bernard Fabreau

The Laboratory for Computer Science and Artificial Intelligence at the Massachusetts Institute of Technology announced the solution of a landmark crypto puzzle. It was specially developed in 1999 to check the forecasts of the then leading IT luminaries regarding the pace of development of the industry. Initially, it was believed that it would take about 35 years to find a solution to the problem, but two independent applicants coped 15 years faster.

The puzzle is not very difficult on its own, but it is designed according to the principle of "testable delay function" - that is, the answer can only be obtained after a certain number of steps. To exclude the possibility of using parallel computing, to remove the temptation to use supercomputers to solve a problem, the authors added several conditions. Basically, you need to do the sequential squaring of the original number 80 trillion times as quickly as possible.

As Ron Rivest, one of the authors of the crypto puzzle, explains, the idea was to keep track of how the computing power would change to perform the squaring operation. And how people will learn how to use them to solve real cryptographic problems, for example, scaling blockchain structures or organizing the security of the use of cryptocurrencies. He admits that he underestimated the pace of development of the industry, so the solution was found much earlier than the predicted date.

The winner was a self-taught programmer Bernard Fabreau from Belgium, who carried out all the necessary calculations for 3.5 years on an ordinary home PC with an Intel Core i7-6700 processor and the GNU Multiple Precision Arithmetic Library. He was competed by the team of Professor Simon Peffers, who used a new squaring algorithm from the scientist Erdinets Oztürk from the University of Sabanci. They used a programmable hardware accelerator FPGA, and it only takes two months to compute the result. But the answer will be received only on May 11, 2019, so the victory was awarded to Fabro.