Time-lock puzzle

A time-lock puzzle hides a solution under a difficulty parameter : generating the puzzle takes time , solving it takes time , and no polynomial-size adversary of depth below distinguishes puzzles for two solutions. The notion and the first candidate are due to RSW96; the definitions below are those of BGJ+16.

Syntax

A time-lock puzzle is a pair of algorithms :

  • , a randomized algorithm that takes a difficulty parameter and a solution and outputs a puzzle ;
  • , a deterministic algorithm that outputs a solution.

is computed by a uniform circuit of size , and runs in time — BGJ+16. BGJ+16 leave implicit in .

Properties

Correctness

is correct if for all , all , all and every in the support of , — BGJ+16.

Security

Adversaries are non-uniform families of polynomial-size circuits, and the depth of is its parallel running time. The difficulty is a polynomial, and are fixed in advance.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{tlp}}_{\mathsf{TLP},\calA,T,s_0,s_1}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$
\State $Z \gets \Gen(1^\secpar, T(\secpar), s_b)$
\State $b' \gets \calA_\secpar(Z)$
\Comment{$\calA_\secpar$ has depth at most $T(\secpar)^\varepsilon$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

is a time-lock puzzle with gap if there is a polynomial such that for every polynomial and every polynomial-size of depth at most ,

is negligible — BGJ+16. The depth bound is necessary because is itself a polynomial-size adversary, of depth , that recovers .

Variations

Weak time-lock puzzles

A weak time-lock puzzle satisfies correctness and security as above, but is only required to be computed by a uniform circuit of size and depth , so generation is fast only in parallel — BGJ+16.

Homomorphic time-lock puzzles

A homomorphic time-lock puzzle lets anyone, without solving them, turn puzzles with solutions into a puzzle with solution whose size and solving time do not grow with the circuit computing ; MT19 introduce the notion and give linearly, multiplicatively and fully homomorphic constructions under concrete assumptions.

TODO: encode the definition of MT19 for a class of circuits (a setup algorithm for , puzzle generation, Solve, Eval, correctness, compactness of evaluated puzzles independent of the circuit size, and security with gap under the quantifiers of the base definition), then register one variant per class, each under its own heading.

Other results

  • Sequential squaring ⇒ TLP (RSW puzzle): the first candidate masks a key with for an RSA modulus , which the generator computes quickly from ; RSW96 conjecture that solving it requires sequential squarings and give no reduction — RSW96.
  • Succinct randomized encodings yield time-lock puzzles assuming a non-parallelizing language exists, that is, a language decidable in time on inputs of length such that, for some , no polynomial-size circuit family of depth at most decides in the worst case; the existence of such a language is necessary for time-lock puzzles. Instantiated with randomized encodings from the literature, the cryptographic assumptions range from one-way functions, whose low-depth non-succinct encodings (garbled circuits) give only weak time-lock puzzles, to indistinguishability obfuscation, whose succinct encodings give time-lock puzzles — BGJ+16.
  • TLP ⇒ OWF: time-lock puzzles imply one-way functions — BGJ+16.
  • No reduction from ROM to TLP: in the random oracle model, a puzzle whose generator makes oracle queries is solved in rounds of polynomially many parallel queries each; a puzzle with a linear gap exists there, generated with one round of parallel queries and requiring rounds of queries to solve — MMV11.

Participates in

Builds on Time-lock puzzle

Produces Time-lock puzzle

Barriers