International Association for Cryptologic Research

International Association
for Cryptologic Research


Transparent Batchable Time-lock Puzzles and Applications to Byzantine Consensus

Shravan Srinivasan , University of Maryland
Julian Loss , CISPA Helmoltz Center for Information Security
Giulio Malavolta , Max Planck Institute for Security and Privacy
Kartik Nayak , Duke University
Charalampos Papamanthou , Yale University
Sri AravindaKrishnan Thyagarajan , NTT Research
DOI: 10.1007/978-3-031-31368-4_20
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Abstract: Time-lock puzzles (TLP) are a fascinating type of cryptographic problem that is easy to generate, but takes a certain time to solve, even when arbitrary parallel speedup is allowed. TLPs have wide-ranging applications including fairness, round efficient computation, and more. To reduce the effort needed to solve large numbers of TLPs, prior work has proposed batching techniques to reduce the cost of solving. However, these proposals either require: (1) a trusted setup or (2) the puzzle size be linear in the maximum batch size, which implies setting an a priori bound on the maximum size of the batch. Any of these limitations restrict the utility of TLPs in decentralized and dynamic settings like permissionless blockchains. In this work, we demonstrate the feasibility and usefulness of a TLP that overcomes all the above limitations using indistinguishability obfuscation to show that there are no fundamental barriers to achieving such a TLP construction. As a main application of our TLP, we show how to improve the resilience of consensus protocols toward network-level adversaries in the following settings: (1) We show a generic compiler that boosts the resilience of a Byzantine broadcast protocol $\Pi$ as follows: if $\Pi$ is secure against $t
  title={Transparent Batchable Time-lock Puzzles and Applications to Byzantine Consensus},
  author={Shravan Srinivasan and Julian Loss and Giulio Malavolta and Kartik Nayak and Charalampos Papamanthou and Sri AravindaKrishnan Thyagarajan},