24
$\begingroup$

Ron Rivest posed a puzzle in 1999. MIT LCS35 Time Capsule Crypto-Puzzle.

The problem is to compute $2^{2^t} \pmod n$ for specified values of $t$ and $n$. Here $n$ is the product of two large primes, and $t$ is chosen to set the desired level of difficulty of the puzzle.

Note that the puzzle can be solved by performing $t$ successive squarings modulo $n$, beginning with the value $2$. That is, set

  • $W(0) = 2$,
  • $W(i+1) = W(i)^2 \pmod n \quad$ for $i\ge0$,

and compute $W(t)$. There is no known way to perform this computation more quickly without knowing the factorization of $n$.

In 1999 they predicted that we'd have 10 GHz processors by now. I realise that raw GHz is a dumb way to measure speed, but how fast are computers for this kind of "intrinsically sequential" computing?

I guess my questions are:

1) What is the state of the art for computation which can not be parallelised?

2) Has anyone claimed to make any progress with this challenge?

Improve this question
$\endgroup$
2
  • $\begingroup$ The answer of Tacticalcoder deserves points. $\endgroup$
    – kelalaka
    Apr 30, 2019 at 18:10
  • 2
    $\begingroup$ @kelalaka That's the answer I started the bounty for. :P $\endgroup$
    – forest ♦
    Apr 30, 2019 at 19:14

4 Answers 4

Reset to default
28
+50
$\begingroup$

2) Has anyone claimed to make any progress with this challenge?

Ah that question I can answer now...

I found the solution on the 15th of April 2019 and sent it to the MIT's CSAIL on the 16th of April. Another team shall have the answer by the 11th or 12th of May (they used a FPGA).

I noticed around the end of 2015 that if I used GMP I could find the answer on my Core i7-6700 CPU in about three years and a half. So I basically let my computer open 24/7 so that it'd solve the "puzzle".

The secret message and the two primes shall be announced on the 15th of May during a ceremony where the "time capsule" shall be opened.

Link to the CSAIL's article about it:

Programmers solve MIT’s 20-year-old cryptographic puzzle

Improve this answer
$\endgroup$
11
  • 8
    $\begingroup$ Congratulations then. Can you offer any small hints to the solution without spoiling the party? $\endgroup$
    – Paul Uszak
    Apr 30, 2019 at 0:12
  • 6
    $\begingroup$ Welcome to crypto.stackexchange - I have to say, it would be nice to see an outline of how your solution worked. If you're allowed and have the time, please consider editing it into your answer. $\endgroup$
    – Ella Rose
    Apr 30, 2019 at 0:30
  • 2
    $\begingroup$ @nealmcb I imagine that has been accomplished by sending it to MIT. $\endgroup$
    – forest ♦
    May 1, 2019 at 0:24
  • 4
    $\begingroup$ @nealmcb: The MIT's CSAIL and Ron Rivest publicly confirmed I was the first one to find the solution but... Four days before that the Antpool Bitcoin mining pool did put a personnalized block header in Bitcoin block #573 138 congratulating me for solving LCS35 : ) So technically Antpool were the first to announce LCS35 was solved. Not a proof yet: the solution is going to be revealed on the 15th of May. $\endgroup$
    – TacticalCoder
    May 1, 2019 at 18:41
  • 1
    $\begingroup$ @nealmcb: yes it's better than in a tx: it's in the block itself as you noticed, which is really amazing because it requires to find a block, which only a mining pool can do nowadays for Bitcoin (huge thanks to the guys at the Antpool mining pool for immortalizing this). I don't know about these non-ASCII bytes: I noticed that too but didn't check that yet... Maybe chinese characters? $\endgroup$
    – TacticalCoder
    May 4, 2019 at 21:17
9
$\begingroup$

The puzzle has now been solved!

The solution was announced in May 2019. It was solved by Bernard Fabrot, who used a modern optimized implementation of big integer multiplication to speed up the computation and finish it in about 3.5 years of computation instead of 35 years. At around the same time, a second team using FPGAs reported being weeks away from a solution, after about 2 months of computation. Congratulations to both of them.

The theory is explained in the research paper that introduced the idea:

The paper is cited in Rivest's description of the time capsule.

As the security analysis in that paper explains, there is no known way to use parallelism (including, e.g., multi-core machines) to speed up the repeated squaring process to any significant degree. The only known way that parallelism helps is to provide a modest speedup for each individual squaring operation; a multi-core machine may be able to compute the modular squaring operation a bit faster than a single-core machine, but the overall speedup available in this fashion is limited. For example, here is a quote from the paper:

repeated squaring seems to be an "intrinsically sequential" process. We know of no obvious way to parallelize it to any large degree. (A small amount of parallelization may be possible within each squaring.) Having many computers is no better than having one. (But having one fast computer is better than one slow one.) The degree of variation in how long it might take to solve the puzzle depends on the variation in the speed of single computers, and not on one's total budget. Since the speed of hardware available to individual consumers is within a small constant factor of what is available to large intelligence organizations, the difference in time to solution is reasonably controllable.

As far as I know, this remains an accurate description of the state of the art.

Improve this answer
$\endgroup$
2
  • $\begingroup$ For the complexity-theory-minded folks at home, 'intrinsically sequential' ~ P-complete. The intrinsic assumption is that there exist problems in P not in NC. This seems likely but it is yet unproven. $\endgroup$
    – pg1989
    Aug 8, 2013 at 6:30
  • $\begingroup$ Has $w$ (or $W(t)$ as it's called here) been published online? The time capsule should be open now, right ? $\endgroup$
    – Henno Brandsma
    May 26, 2019 at 22:51
3
$\begingroup$

Unless $2^t$ is the order of $2$ in the group $\mathbb Z_n$, in which case the solution is trivial.

Unless the factors of $n$ are known, in which case the Chinese remainder theorem can be used.

Unless $n$ (or its factors) has a special form, with only a few sparse bits being set (e.g. $n = 2^a + 2^b + 1$) and similar cases where $n$ has only a few alternations between $1$s and $0$s in its binary expansion, in which case there are possibly fast reduction methods.

The case where $n$ is a power of $2$ minus $1$ and $t = n-1$ is the Great Internet Mersenne Prime Search and it is where you would find the state of the art of "fast" specialized software.

Quantum computing? From en.wikipedia.org/wiki/Shor's_algorithm: "In 2012, the factorization of 15 was repeated.[7] Also in 2012, the factorization of 21 was achieved, setting the record for the largest number factored with a quantum computer" .... "The runtime bottleneck of Shor's algorithm is quantum modular exponentiation" . Still slow, and still impractical for large numbers .....

I am not aware of any proof that the problem can't be solved for general values of $t$ and $n$, neither that dependent steps of repeated squaring is the only solution.

After all, using a normal basis, squaring can be replaced by circular shifts. Have a look at http://en.wikipedia.org/wiki/Normal_basis.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ If that factors of $n$ are known, you don't even need the CRT. You have enough information to reduce $2^t ~ \text{mod} ~ \varphi{(n)}$ and efficiently solve the puzzle. $\endgroup$
    – Thomas
    Jan 10, 2013 at 3:58
  • 4
    $\begingroup$ @Pierre, this is pretty much covered in Rivest's scientific paper that goes with this. (The chances that $2^t$ is the order of $2$ in the group is vanishingly small. Part of the whole point is that $n$ is chosen so that it is hard to factor, and its factors are not known. And so on.) $\endgroup$
    – D.W.
    Jan 10, 2013 at 6:34
2
$\begingroup$

Amazingly enough, the puzzle was solved a few weeks after @TacticalCoder got an answer, on May 10, as described at https://www.cryptophage.com. Their solution worked in 2 months, rather than nearly 4 years, since they used FPGA hardware optimized for this task. And I think they declared to the LCS that they expected to solve it, just hours after @TacticalCoder wrote to LCS. A real shock for everyone!

They also tweeted the SHA-256 hash of their solution on that day: 1310966a15298e756b1d2533a9316eb2e2a582a492841a71f15a04a264ce2ae6

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.