Time-Lock Puzzle

What Is a Time-Lock Puzzle?

A time-lock puzzle is a cryptographic primitive that encodes a secret so it can only be recovered after performing a specific amount of sequential work. Unlike standard encryption where a key holder can decrypt instantly, a time-lock puzzle forces anyone without a trapdoor to spend a predictable duration computing the answer, step by step, with no shortcut through parallelism.

The concept was introduced in 1996 by Ronald Rivest, Adi Shamir, and David Wagner in their paper "Time-lock Puzzles and Timed-release Crypto." Their motivation was timed-release encryption: sending a message "into the future" so that no one, not even the sender, can read it before a predetermined time has passed, without relying on a trusted third party to hold the secret.

Time-lock puzzles have since found applications in sealed-bid auctions, fair contract signing, unbiased randomness generation, and private voting protocols. They are also a foundational building block for verifiable delay functions (VDFs), which add efficient public verifiability.

How It Works

The Rivest-Shamir-Wagner (RSW) construction relies on the fact that repeated squaring modulo an RSA composite is inherently sequential. Each squaring depends on the result of the previous one, so even a solver with millions of processors can only compute one step at a time.

Puzzle Generation

The puzzle creator performs the following steps:

1. Choose two large random primes p and q, and compute the RSA modulus N = p × q
2. Compute Euler's totient: φ(N) = (p − 1)(q − 1). This value is the trapdoor
3. Set the time parameter T = S × Δ, where S is the estimated maximum squarings per second and Δ is the desired lock duration
4. Choose a random base value r from the integers modulo N
5. Using the trapdoor, efficiently compute e = 2^T mod φ(N), then w = r^e mod N. This is the puzzle solution, computed in O(log T) time
6. Encrypt the secret message m using w as a key (for example, c = m + w mod N)
7. Publish the puzzle as (N, T, r, c) and destroy p, q, and φ(N)

Puzzle Solving

Without the factorization of N, the solver must compute w = r^2T mod N by performing T successive squarings:

w₀ = r
w₁ = w₀² mod N
w₂ = w₁² mod N
...
wₜ = wₜ₋₁² mod N

# After T squarings, wₜ = r^(2^T) mod N
# Recover the secret: m = c - wₜ mod N

Each squaring requires the result of the previous step, making the computation strictly sequential. The solver cannot skip ahead or distribute the work across multiple machines. With the trapdoor (φ(N)), the creator reduces the exponent first (2^T mod φ(N)) and computes the result in O(log T) operations instead of T.

Why Parallelism Does Not Help

The security of time-lock puzzles rests on the sequential squaring assumption: given a random r and composite N whose factorization is unknown, computing r^2T mod N requires T sequential multiplications. Unlike hash function preimage searches or proof-of-work mining where more processors directly reduce solving time, each step in repeated squaring depends on the output of the prior step. A thousand GPUs offer no advantage over a single core.

A Real-World Example: The LCS35 Time Capsule

In 1999, Rivest created a concrete time-lock puzzle called LCS35 to celebrate MIT's Laboratory for Computer Science. The puzzle used a 2048-bit RSA modulus and required approximately 80 trillion successive squarings, designed to take roughly 35 years accounting for Moore's Law improvements in hardware speed.

Belgian programmer Bernard Fabrot solved it in April 2019 after 3.5 years of continuous computation on a consumer Intel Core i7 processor. Simultaneously, a team using custom FPGA hardware was on track to solve the same puzzle in approximately two months. The puzzle was cracked 15 years ahead of schedule, vividly illustrating the difficulty of calibrating time-lock puzzles against unpredictable hardware advances.

Time-Lock Puzzles vs. Verifiable Delay Functions

Verifiable delay functions (VDFs), formalized by Boneh, Bonneau, Bünz, and Fisch in 2018, share the sequential computation requirement of time-lock puzzles but add a critical property: efficient public verifiability.

Most VDF constructions (including those by Wesolowski and Pietrzak) build on the same repeated squaring structure as RSW time-lock puzzles, but add compact proofs that allow anyone to verify correctness in polylogarithmic time. Time-lock puzzles, by contrast, offer no efficient verification without the trapdoor: the only way to check a claimed solution is to solve the puzzle yourself or know the secret factorization.

For a deeper look at how delay-based cryptography applies to blockchain consensus and randomness, see the research article on zero-knowledge proofs and Bitcoin applications.

Bitcoin Timelocks: A Simpler Alternative

While time-lock puzzles enforce delays through raw computation, Bitcoin offers consensus-level timelocks that enforce delays through protocol rules. These are simpler, more predictable, and do not require sequential computation.

OP_CHECKLOCKTIMEVERIFY (CLTV), defined in BIP 65 and deployed in late 2015, makes a transaction output unspendable until a specified block height or Unix timestamp. The spending transaction's nLockTime must meet or exceed the CLTV value, and miners enforce this rule by rejecting non-compliant transactions.

# Bitcoin Script using CLTV
# Funds locked until block 900000
OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY
900000 OP_CHECKLOCKTIMEVERIFY OP_DROP
OP_CHECKSIG

The distinction is fundamental: CLTV relies on the blockchain network for enforcement (miners validate the constraint), while time-lock puzzles rely on computational hardness (physics and mathematics enforce the delay). CLTV provides exact, deterministic time guarantees tied to block height. Time-lock puzzles provide approximate guarantees that depend on the solver's hardware.

Bitcoin also offers OP_CHECKSEQUENCEVERIFY (CSV) for relative timelocks (delays measured from when an output was confirmed). Together, CLTV and CSV power HTLCs, payment channels, and the Lightning Network without requiring any sequential computation puzzle.

Use Cases

Timed-Release Encryption

The original application: encrypting data so it becomes accessible only after a specified duration. A journalist could publish encrypted evidence that automatically becomes decryptable after a deadline, without trusting any server to hold the key.

Sealed-Bid Auctions

Bidders encapsulate their bids as time-lock puzzles during the bidding phase. All bids remain confidential until the deadline, when the auctioneer (or anyone) can solve the puzzles to reveal them. No bidder can see others' bids before committing, and no trusted party is needed to manage sealed envelopes.

Fair Contract Signing

When two mutually suspicious parties need to exchange digital signatures on a contract, time-lock puzzles provide gradual fairness. Each party wraps their signature in a puzzle. If one party aborts, the other can recover both signatures by solving the puzzles: the time investment is comparable for both sides. This is an application of timed commitments, as formalized by Boneh and Naor.

Private Voting

Homomorphic time-lock puzzles, introduced by Malavolta and Thyagarajan in 2019, enable evaluating functions over encrypted puzzles without solving them individually. For private voting, each ballot is encoded as a puzzle. The puzzles can be homomorphically combined to produce a single puzzle whose solution is the election tally, meaning only one puzzle must be solved to reveal the aggregate result while individual votes remain private.

Risks and Considerations

Hardware Acceleration

Time-lock puzzles are "step-lock" puzzles, not true time-locks: they guarantee a number of sequential operations, not a duration. Custom hardware (ASICs, FPGAs) can perform modular squarings dramatically faster than general-purpose CPUs. The LCS35 puzzle demonstrated this starkly: a 35-year estimate was beaten in 3.5 years on consumer hardware, and an FPGA approach was on track to finish in two months. Calibrating delay against future hardware advances is inherently speculative.

Trusted Setup

The puzzle creator knows the factorization of N (primes p and q). If they fail to destroy this knowledge, or if the generation process is compromised, the puzzle can be solved instantly. For multi-party applications like voting, this requires either a trusted party, a multi-party computation ceremony where participants jointly generate N without any individual learning its factors, or alternative algebraic structures like class groups of imaginary quadratic fields that require no trusted setup at all.

Quantum Computing Threat

Shor's algorithm can factor large integers exponentially faster than any known classical algorithm. A sufficiently powerful quantum computer could factor N, recover φ(N), and solve any RSA-based time-lock puzzle instantly. No post-quantum construction for repeated-squaring time-lock puzzles is currently known.

No Efficient Verification

Unlike VDFs, standard time-lock puzzles provide no way for a third party to quickly verify a claimed solution without either solving the puzzle independently or possessing the trapdoor. This limits their usefulness in decentralized protocols where public verifiability is essential. Research into verifiable time-lock puzzles is ongoing, with recent work on "check-before-you-solve" constructions that allow pre-solution verification.

Calibration Difficulty

Setting the time parameter T requires estimating the solver's maximum computation speed S, which depends on hardware that may not exist yet. Overestimating S leads to puzzles that unlock too soon; underestimating means the secret stays locked longer than intended. This imprecision makes time-lock puzzles unsuitable for applications requiring exact deadlines, where blockchain-based timelocks are preferable.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.