Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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. I don't know of anyone who has claimed any progress on the puzzle.

share|improve this answer
    
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. –  pg1989 Aug 8 '13 at 6:30

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.

share|improve this answer
2  
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. –  Thomas Jan 10 '13 at 3:58
4  
@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.) –  D.W. Jan 10 '13 at 6:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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