Paper 2023/1582

Time-Lock Puzzles with Efficient Batch Solving

Jesko Dujmovic, Helmholtz Center for Information Security, Saarland University
Rachit Garg, The University of Texas at Austin
Giulio Malavolta, Bocconi University, Max Planck Institute for Security and Privacy

Time-Lock Puzzles (TLPs) are a powerful tool for concealing messages until a predetermined point in time. When solving multiple puzzles, it becomes crucial to have the ability to "batch-solve" puzzles, i.e., simultaneously open multiple puzzles while working to solve a "single one". Unfortunately, all previously known TLP constructions equipped for batch solving rely on super-polynomially secure indistinguishability obfuscation, making them impractical. In light of this challenge, we present novel TLP constructions that offer batch-solving capabilities without using heavy cryptographic hammers. Our proposed schemes are simple and concretely efficient, and they can be constructed based on well-established cryptographic assumptions based on pairings or learning with errors (LWE). Along the way, we introduce new constructions of puncturable key-homomorphic PRFs both in the lattice and in the pairing setting, which may be of independent interest. Our analysis leverages an interesting connection to Hall's marriage theorem and incorporates an optimized combinatorial approach, enhancing the practicality and feasibility of our TLP schemes. Furthermore, we introduce the concept of "rogue-puzzle attacks", where maliciously crafted puzzle instances may disrupt the batch-solving process of honest puzzles. We then propose constructions of concrete and efficient TLPs designed to prevent such attacks.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2024
time lock puzzlesbatch solvingkey homomorphic prf
Contact author(s)
jesko dujmovic @ cispa de
rachg96 @ cs utexas edu
giulio malavolta @ hotmail it
2024-02-29: revised
2023-10-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jesko Dujmovic and Rachit Garg and Giulio Malavolta},
      title = {Time-Lock Puzzles with Efficient Batch Solving},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1582},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.