How would we design a fast circuit to solve LCS35? LCS35 is a time-lock puzzle, stated in Ronald L. Rivest's Description of the LCS35 Time Capsule Crypto-Puzzle [1] (April 1999). That instantiates a system in Ronald L. Rivest, Adi Shamir and David A. Wagner's Time-Lock puzzles and timed-release Crypto [2] (MIT technical report, 1996, revised March 1999).

Solving the puzzle boils down to computing $2^{(2^t)}\bmod n$ for $n$ a public 2046-bit RSA modulus of secret factorization, and $t\approx1.13\cdot2^{46}$. The reference method sequentially computes $w_i=2^{(2^i)}\bmod n$ for $i$ up to $t$, by iterating $w_{i+1}\gets w_i^2\bmod n$, starting from $w_0=2$, or perhaps $w_{10}=2^{1024}$.

How would we design a fast circuit for that purpose? And what speed (in equivalent modular squaring per second) could it achieve? I'm interested in


Mathematical techniques: e.g. would Montgomery arithmetic help?
Architectural tradeoffs: e.g. between circuit depth and size, both causing a slowdown.
Technology: I do not even know what technology is currently the state of the art when it comes to fast logic, much less what it could realistically achieve.


The design of LCS35 attempts to block attempts at massive parallelization, and mostly succeeds as far as we know. The question is about making the computation nevertheless.

The value of $t$ was chosen assuming 3000 squaremods/second in 1999, exponential grows to ×13 that per 2012, then again ×5 per 2034 (the challenge ends in 2033).



I propose to ignore:


Operating cost: it would be negligible compared to bitcoin mining, unless we find a way to parallelize, which would be a major breakthru.
Investment cost: it depends on too many factors, and evaluations are not falsifiable.
Computation errors, since we know how to deal with them:


Reference [1] suggests making the computation of $w'_i=2^{(2^i)}\bmod(c\,n)$ where $c$ is a moderate prime (50-bit). This allows a periodical check that $w'_i\bmod c\ =\ 2^{(2^i)\bmod (c'-1)}\bmod c$, backtracking if an error creeps, and getting $w_t\gets w'_t\bmod n$ in the end.
A variant is to compute both $w'_i=2^{(2^t)}\bmod(3n)$ and $w''_i=2^{(2^t)}\bmod(5n)$ on two independent engines (conveniently, both moduli are 2048-bit), and periodically check that $w'_i\bmod n=w''_i\bmod n$. That requires two independent implementations but little increase in the modulus size, hence (I guess) faster computation and smaller computing engines.

Attacks that essentially factor $n$, including using a Quantum Computer.
Alternatives to LCS35 for timed-release crypto, as asked in this other question.
Turns out the LCS35 problem was first solved on April 15, 2019 by Bernard Fabrot. It took 3.5 years of runtime on a single core of a standard modern CPU, using GMP.

Independently, the Cryptophage project solved LCS35 in less than 2 months, starting mid March 2019, using an FPGA-based system that performs modular squaring with extremely low latency.