Paper 2020/730
On the Security of Time-Lock Puzzles and Timed Commitments
Jonathan Katz, Julian Loss, and Jiayu Xu
Abstract
Time-lock puzzles---problems whose solution requires some amount of 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: - We give the first hardness result about the sequential-squaring conjecture in a non-generic model. Namely, in a quantitative version of the algebraic group model (AGM) that we call the strong AGM, we show that speeding up sequential squaring is as hard as factoring $N$. - We then focus on 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 non-malleable timed commitments. As a building block of independent interest, we also define (and give constructions for) a related primitive called timed public-key encryption.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in TCC 2020
- Keywords
- Time-lock puzzlestimed commitmentsalgebraic group model
- Contact author(s)
-
jkatz2 @ gmail com
lossjulian @ gmail com
jiayux @ uci edu - History
- 2020-10-29: revised
- 2020-06-17: received
- See all versions
- Short URL
- https://ia.cr/2020/730
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/730,
author = {Jonathan Katz and Julian Loss and Jiayu Xu},
title = {On the Security of Time-Lock Puzzles and Timed Commitments},
howpublished = {Cryptology ePrint Archive, Paper 2020/730},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/730}},
url = {https://eprint.iacr.org/2020/730}
}
