Paper 2024/676

Composing Timed Cryptographic Protocols: Foundations and Applications

Karim Eldefrawy, SRI International
Benjamin Terner, Confidencial
Moti Yung, Google (United States) and Columbia University

Time-lock puzzles are unique cryptographic primitives that use computational complexity to keep information secret for some period of time, after which security expires. Unfortunately, current analysis techniques of time-lock primitives provide no sound mechanism to build multi-party cryptographic protocols which use expiring security as a building block. We explain in this paper that all other attempts at this subtle problem lack either composability, a fully consistent analysis, or functionality. The subtle flaws in the existing frameworks reduce to an impossibility by Mahmoody et al., who showed that time-lock puzzles with super-polynomial gaps (between committer and solver) cannot be constructed from random oracles alone; yet still the analyses of algebraic puzzles today treat the solving process as if each step is a generic or random oracle. This paper presents a new complexity theoretic based framework and new structural theorems to analyze timed primitives with full generality and in composition (which is the central modular protocol design tool). The framework includes a model of security based on fine-grained circuit complexity which we call residual complexity, which accounts for possible leakage on timed primitives as they expire. Our definitions for multi-party computation protocols generalize the literature standards by accounting for fine-grained polynomial circuit depth to model computational hardness which expires in feasible time. Our composition theorems incur degradation of (fine-grained) security as items are composed. In our framework, simulators are given a polynomial “budget” for how much time they spend, and in composition these polynomials interact. Finally, we demonstrate via a prototypical auction application how to apply our framework and theorems. For the first time, we show that it is possible to prove – in a way that is fully consistent, with falsifiable assumptions – properties of multi-party applications based on leaky, temporarily secure components.

Available format(s)
Publication info
multiparty computationtime-lock puzzlefine grained
Contact author(s)
karim eldefrawy @ sri com
ben terner @ confidencial io
motiyung @ gmail com
2024-05-03: approved
2024-05-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Karim Eldefrawy and Benjamin Terner and Moti Yung},
      title = {Composing Timed Cryptographic Protocols: Foundations and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2024/676},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.