This week MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) announced that a 20-year-old cryptographic puzzle was just solved by a self-taught programmer from Belgium, 15 years earlier than MIT scientists expected.
Bernard Fabrot spent the last three and a half years computing the solution to a puzzle first announced by MIT researchers in 1999. Separately, another team led by tech executive Simon Peffers is nearing completion of computing a solution.
The puzzle essentially involves doing roughly 80 trillion successive squarings of a starting number, and was specifically designed to foil anyone trying to solve it more quickly by using parallel computing.
Fabrot and Peffers took very different approaches to the puzzle. Fabrot used a simple Intel Core i7-6700 found in consumer PCs, and computed the solution using the GNU Multiple Precision Arithmetic Library (GMP). Meanwhile, Peffers' team used a novel squaring algorithm (designed by Erdinç Öztürk from Sabanci University) to run on a programmable hardware accelerator called an FPGA. The team, which is working as part of a collaboration called Cryptophage, is on track to finish the puzzle on May 11 after only two months of computation.
“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 tied to a celebration of 35 years of research at MIT’s Laboratory for Computer Science (now CSAIL). “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.”
The puzzle is an example of a “verifiable delay function” (VDF), meaning that its answer can only be solved after a certain number of steps. Because VDFs can also be used to create unbiased randomness, they’ve been proposed as potential approaches to improve the security and scalability of blockchain systems like Ethereum and Filecoin.
In the original announcement, LCS promised that, if a correct solution was uncovered, they would open a special “time capsule” designed by architect Frank Gehry and filled with historical artifacts from the likes of Web inventor Tim Berners-Lee, Ethernet co-inventor Bob Metcalfe, and Microsoft founder Bill Gates. (Gates donated the original Altair BASIC that represented Microsoft’s first-ever product, which they developed for MITS in 1975.)
The capsule ceremony will happen Wednesday, May 15 at 4 p.m. at MIT’s Stata Center.