CISPA
Browse
2020-730.pdf (464.17 kB)

On the Security of Time-Locked Puzzles and Timed Commitments.

Download (464.17 kB)
preprint
posted on 2024-03-20, 13:48 authored by Jonathan Katz, Julian Loss, Jiayu Xu
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 mod 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 in a non-generic model of computation. Namely, in a quantitative version of the algebraic group model (AGM) that we call the strong AGM, we show that any speed up of sequential squaring is as hard as factoring N . 2. 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

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

BibTeX

@misc{Katz:Loss:Xu:2020, title = "On the Security of Time-Locked Puzzles and Timed Commitments.", author = "Katz, Jonathan" AND "Loss, Julian" AND "Xu, Jiayu", year = 2020, month = 1 }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC