Paper 2024/676

Composing Timed Cryptographic Protocols: Foundations and Applications

Abstract

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, twenty-five years after their introduction, 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. As pointed out recently in the peer-reviewed literature, current attempts at this problem lack either composability, a fully consistent analysis, or functionality. 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, in turn, incur degradation of (fine-grained) security as items are composed. In our framework, simulators are given a polynomial ``budget" for computational depth, 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. This work therefore significantly extends provable cryptography down from the self-contained world of arbitrary-polynomial security to the realm of small time domains which often appear in practice, where security of components expires while the larger system remains secure.