TARDIS: a foundation of time-lock puzzles in UC

Carsten Baum, Bernardo David, Rafael Dowsley, Jesper Buus Nielsen, Sabine Oechsner

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Time-based primitives like time-lock puzzles (TLP) are finding widespread use in practical protocols, partially due to the surge of interest in the blockchain space where TLPs and related primitives are perceived to solve many problems. Unfortunately, the security claims are often shaky or plainly wrong since these primitives are used under composition. One reason is that TLPs are inherently not UC secure and time is tricky to model and use in the UC model. On the other hand, just specifying standalone notions of the intended task, left alone correctly using standalone notions like non-malleable TLPs only, might be hard or impossible for the given task. And even when possible a standalone secure primitive is harder to apply securely in practice afterwards as its behavior under composition is unclear. The ideal solution would be a model of TLPs in the UC framework to allow simple modular proofs. In this paper we provide a foundation for proving composable security of practical protocols using time-lock puzzles and related timed primitives in the UC model. We construct UC-secure TLPs based on random oracles and show that using random oracles is necessary. In order to prove security, we provide a simple and abstract way to reason about time in UC protocols. Finally, we demonstrate the usefulness of this foundation by constructing applications that are interesting in their own right, such as UC-secure two-party computation with output-independent abort.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2021
Subtitle of host publication40th Annual International Conference on the Theory and Applications of Cryptographic Techniques Zagreb, Croatia, October 17–21, 2021 Proceedings, Part III
EditorsAnne Canteaut, François-Xavier Standaert
Place of PublicationCham Switzerland
PublisherSpringer
Pages429-459
Number of pages31
ISBN (Electronic)9783030778835
ISBN (Print)9783030778828
DOIs
Publication statusPublished - 2021
Event40th Annual International Conference on the Theory and Applications of Cryptographic Techniques 2021 - Zagreb, Croatia
Duration: 17 Oct 202121 Oct 2021
Conference number: 40th
https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/978-3-030-77883-5 (Proceedings)
https://eurocrypt.iacr.org/2021/ (Website)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12698
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference40th Annual International Conference on the Theory and Applications of Cryptographic Techniques 2021
Abbreviated titleEUROCRYPT 2021
Country/TerritoryCroatia
CityZagreb
Period17/10/2121/10/21
Internet address

Cite this