MIT’s Computer Science and Artificial Intelligence Laboratory’s (CSAIL) recently announced that a self-taught programmer from Belgium solved MIT’s 20-year-old cryptographic puzzle 15 years earlier than MIT scientists expected. The programmer, Bernard Fabrot, had been working for 3 and a half years on a solution to the enigma. His method was actually rather simple, using an Intel Core i7-6700 found in consumer PCs and using the GNU Multiple Precision Arithmetic Library (GMP) to compute the solution.
The puzzle was first announced by MIT researchers in 1999 and requires the programmer to do around 80 trillion successive squarings of a starting number. The catch, however, is that it was specifically designed to prevent anyone from being able to solve the puzzle throug parallel computing. The problem is an example of “verifiable delay function” (VDF), in which the solver must take a certain number of steps in order to reach a solution.
A separate team led by tech executive Simon Peffers is not far behind Fabrot, who is employing a much different method. The team is using a novel squaring algorithm designed by Erdinç Öztürk from Sabanci University to run on a programmable hardware accelerator called an FPGA. The team is part of a collaboration called Cryptophage and, after only two months of computing, plans to have a solution by May 11th, 2019.
“There have been hardware and software advances beyond what I predicted in 1999,” says MIT professor Ron Rivest, who first announced the puzzle in April 1999 and tied the solving to MIT’s Laboratory for Computer Science’s (now CSAIL) celebration of 35 years of research. “The puzzle’s fundamental challenge of doing roughly 80 trillion squarings remains unbroken, but the resources required to do a single squaring have been reduced by much more than I predicted.”
When MIT’s Laboratory for Computer Science first released the puzzle in 1999, they promised that once the problem was solved, they would open a special “time capsule” designed by architect Frank Gehry that’s filled with historical artifacts that express the brilliance of Web inventor Tim Berners-Lee, Ethernet co-inventor Bob Metcalfe, and Microsoft founder Bill Gates. The capsule ceremony will take place Wednesday, May 15 at 4 p.m. at MIT’s Stata Center.
If you enjoyed this article and want to receive more valuable industry content like this, click here to sign up for our digital newsletters!
Leave a Reply