Mind-Bending Cryptography Puzzle Gets an ‘Early’ Solution After Just 20 Years
All the way back in 1999, when the Massachusetts Institute of Technology Laboratory for Computer Science was celebrating its 35th year of research, it gave itself an unusual birthday present: a large lead container, shaped like a paper bag, sculpted by legendary architect Frank Gehry.
It was sealed away behind a cryptographic puzzle, specifically designed to take around 35 years to solve. It’s based on Moore’s law that an integrated circuit doubles biannually, and as the next answer relies on the previous one, it’s impossible to cheat. A self-taught programmer has just completed it in under four years.
Inside is a collection of great innovations in computer science, from the likes of Bill Gates, Bob Metcalfe and Tim Berners-Lee, among others, which will soon see the light of day, 15 years earlier than the expected date of 2034.
Bernard Fabrot of Belgium spent the last three and a half years working on the solution, using simple tools – an Intel Core i7-6700 processor running free software, the GNU Multiple Precision Arithmetic Library (GMP).
“The puzzle is designed to foil attempts of a solver to exploit parallel or distributed computing to speed up the computation,” the puzzle’s architect, MIT professor Ron Rivest, said in 1999. “The computation required to solve the puzzle is ‘intrinsically sequential’.”
The puzzle involves performing 80 trillion squarings of a starting number, in sequence, one step at a time. So, say you start with 3, you’d square that to get 9, which you’d square to get 81, and so on and so forth, 80 trillion times.
You can’t cheat by running the calculations simultaneously, because you need the number from the previous calculation to proceed.
When all the calculations have been performed, the final number can be used in conjunction with a number provided to reveal a short sentence congratulating the solver. It is this sentence that is submitted as proof of the solution.
So how did Fabrot solve it so quickly? Well, our technology got a lot better a lot faster than anticipated.
“There have been hardware and software advances beyond what I predicted in 1999,” Rivest said.
“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.”
And it’s not a particularly difficult puzzle – just time- and computing-intensive. Fabrot was able to run it as a side project, only checking the intermediate results once in a while to make sure the squarings were still on the right track, backing up the results, and keeping the computer running.
“I basically used my everyday workstation. There were 79 trillions operations to be made and I’d save the intermediate result every 1 billion result (so approximately every 22 minutes I’d save a result),” he wrote on ycombinator’s Hacker News.
“The computation cannot be parallelized and the i7 I was using has four cores. So basically instead of turning it every night off I’d simply leave it running 24/7 … But I coded (totally unrelated things), compiled things from source, browsed the web, did my email, etc. from the very workstation which computed the solution.”
According to Wired, there was a slight hitch though. When he went to hand in the solution to the Laboratory for Computer Science as instructed, Fabrot found it no longer existed, having been merged into MIT’s Computer Science & Artificial Intelligence Laboratory (CSAIL) – and CSAIL’s director wasn’t aware of the puzzle’s existence.
Interestingly, although Fabrot was the first to turn in the solution, he wasn’t the only one working on the puzzle. Tech executive Simon Peffers and the Cryptophage team were running custom software on high-tech field-programmable gate arrays, designed specifically to solve the puzzle.
Peffers and his team are due to have the solution on 11 May, after just two months of computation.
“We didn’t have anyone come to us until these two came up to us on practically the same day to say ‘we’ve solved your problem,'” Rivest told Wired. “That’s an astonishing coincidence.”
The solution to the puzzle will be revealed, and the capsule opened, on 15 May, during a special ceremony to be held at 4PM ET at MIT’s Stata Center.