Paper 2023/439

Standard Model Time-Lock Puzzles: Defining Security and Constructing via Composition

Karim Eldefrawy, SRI International
Sashidhar Jakkamsetti, University of California, Irvine
Ben Terner, University of California, Irvine
Moti Yung, Google (United States), Columbia University
Abstract

The introduction of time-lock puzzles initiated the study of publicly “sending information into the future.” For time-lock puzzles, the underlying security-enabling mechanism is the computational complexity of the operations needed to solve the puzzle, which must be tunable to reveal the solution after a predetermined time, and not before that time. Time-lock puzzles are typically constructed via a commitment to a secret, paired with a reveal algorithm that sequentially iterates a basic function over such commitment. One then shows that short-cutting the iterative process violates cryptographic hardness of an underlying problem. To date, and for more than twenty-five years, research on time-lock puzzles relied heavily on iteratively applying well-structured algebraic functions. However, despite the tradition of cryptography to reason about primitives in a realistic model with standard hardness assumptions (often after initial idealized assumptions), most analysis of time-lock puzzles to date still relies on cryptography modeled (in an ideal manner) as a random oracle function or a generic group function. Moreover, Mahmoody et al. showed that time-lock puzzles with superpolynomial gap cannot be constructed from random-oracles; yet still, current treatments generally use an algebraic trapdoor to efficiently construct a puzzle with a large time gap, and then apply the inconsistent (with respect to Mahmoody et al.) random-oracle idealizations to analyze the solving process. Finally, little attention has been paid to the nuances of composing multi-party computation with timed puzzles that are solved as part of the protocol. In this work, we initiate a study of time-lock puzzles in a model built upon a realistic (and falsifiable) computational framework. We present a new formal definition of residual complexity to characterize a realistic, gradual time-release for time-lock puzzles. We also present a general definition of timed multi-party computation (MPC) and both sequential and concurrent composition theorems for MPC in our model.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Time-lock puzzlesmulti-party computationcomposition
Contact author(s)
karim eldefrawy @ sri com
sjakkams @ uci edu
bterner @ uci edu
moti @ google com
History
2023-03-27: approved
2023-03-26: received
See all versions
Short URL
https://ia.cr/2023/439
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/439,
      author = {Karim Eldefrawy and Sashidhar Jakkamsetti and Ben Terner and Moti Yung},
      title = {Standard Model Time-Lock Puzzles: Defining Security and Constructing via Composition},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/439},
      year = {2023},
      url = {https://eprint.iacr.org/2023/439}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.