# My example of Time-lock-puzzles-and-timed-release-Crypt (cpp)

Time Capsule Crypto-Puzzle

My MSVC example: Time-lock-puzzles-and-timed-release-Crypto.rar (MSVC)

Description:

lcs35-puzzle-description.txt

Timelock puzzles and timedrelease Crypto (PDF)

The puzzle is designed to foil attempts of a solver to exploit

parallel or distributed computing to speed up the computation. The

computation required to solve the puzzle is "intrinsically

sequential".

The problem is to compute 2^(2^t) (mod 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) (mod n) for i>0,

and compute W(t). There is no known way to perform this computation

more quickly without knowing the factorization of n.

The value of t was chosen to take into consideration the growth in

computational power due to "Moore's Law". Based on the SEMATECH

National Technology Roadmap for Semiconductors (1997 edition), we can

expect internal chip speeds to increase by a factor of approximately

13 overall up to 2012, when the clock rates reach about 10GHz. After

that improvements seem more difficult, but we estimate that another

factor of five might be achievable by 2034. Thus, the overall rate of

computation should go through approximately six doublings by 2034.

We estimate that the puzzle will require 35 years of continuous

computation to solve, with the computer being replaced every year by

the next fastest model available. Most of the work will really be

done in the last few years, however.

An interesting question is how to protect such a computation from

errors. If you have an error in year 3 that goes undetected, you may

waste the next 32 years of computing. Adi Shamir has proposed a slick

means of checking your computation as you go, as follows. Pick a

small (50-bit) prime c, and perform the computation modulo cn rather

than just modulo n. You can check the result modulo c whenever you

like; this should be a extremely effective check on the computation

modulo n as well.

In order to allow the LCS director in the year 2034 (or whenever) to

verify a submitted solution, we have arranged things so that solving

the puzzle also enables the solver to factor the modulus n, as

described below.

Of course, one way to break the puzzle is to factor the modulus n

directly. But we have chosen a 2048-bit modulus, which is unlikely to

be factored in the given time frame without a breakthrough in the art

of factoring. Just as a failure of Moore's Law could make the puzzle

harder than intended, a breakthrough in the art of factoring would

make the puzzle easier than intended.

Here is a smaller example of the puzzle.

Suppose n = 11*23 = 253, and t = 10. Then we can compute:

2^(2^1) = 2^2 = 4 (mod 253)

2^(2^2) = 4^2 = 16 (mod 253)

2^(2^3) = 16^2 = 3 (mod 253)

2^(2^4) = 3^2 = 9 (mod 253)

2^(2^5) = 9^2 = 81 (mod 253)

2^(2^6) = 81^2 = 236 (mod 253)

2^(2^7) = 236^2 = 36 (mod 253)

2^(2^8) = 36^2 = 31 (mod 253)

2^(2^9) = 31^2 = 202 (mod 253)

w = 2^(2^t) = 2^(2^10) = 202^2 = 71 (mod 253)

Thus, the "w" value computed for the puzzle is 71 (decimal), which is

47 (hex). If we have a "z" value for the puzzle of 13 (hex), then the

"secret message" for the example is (47 xor 13) = 54 (hex). (The secret

message should then be interpreted in ascii at 8 bits per character.)