Paper 2020/730

On the Security of Time-Locked Puzzles and Timed Commitments

Jonathan Katz and Julian Loss and Jiayu Xu

Abstract

Time-locked puzzles---problems whose solution requires some amount of (inherently) sequential effort---have seen a recent increase in popularity (e.g., in the context of verifiable delay functions). Most constructions rely on the conjecture that, given a random~$x$, computing $x^{2^T} \bmod N$ requires at least $T$ (sequential) steps. We study the security of time-locked primitives from two perspectives: We give the first hardness result about the sequential squaring conjecture. Namely, we show that even in (a quantitative version of) the algebraic group model, any speed up of sequential squaring is as hard as factoring~$N$. We then focus on \emph{timed commitments}, one of the most important primitives that can be obtained from time-locked puzzles. We extend existing security definitions to settings that may arise when using timed commitments in higher-level protocols. We then give the first construction of \emph{non-malleable} timed commitments. As a building block of independent interest, we also define (and give constructions for) a new primitive called \emph{time-released public-key encryption}.