CryptoDB
On the Security of Time-Lock Puzzles and Timed Commitments
| Authors: | |
|---|---|
| Download: | |
| Presentation: | Slides |
| Abstract: | Time-lock puzzles—problems whose solution requires some amount of \emph{sequential} effort—have recently received increased interest (e.g., in the context of verifiable delay functions). Most constructions rely on the sequential-squaring conjecture that computing $g^{2^T} \bmod N$ for a uniform~$g$ requires at least $T$ (sequential) steps. We study the security of time-lock primitives from two perspectives: 1. We give the first hardness result about the sequential-squaring conjecture. Namely, in a quantitative version of the algebraic group model (AGM) that we call the \emph{strong} AGM, we show that any speed up of sequential squaring is as hard as factoring $N$. 2. We then focus on \emph{timed commitments}, one of the most important primitives that can be obtained from time-lock puzzles. We extend existing security definitions to settings that may arise when using timed commitments in higher-level protocols, and 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 related primitive called \emph{timed public-key encryption}. |
Video from TCC 2020
BibTeX
@article{tcc-2020-30628,
title={On the Security of Time-Lock Puzzles and Timed Commitments},
booktitle={Theory of Cryptography},
publisher={Springer},
author={Jonathan Katz and Julian Loss and Jiayu Xu},
year=2020
}