Paper 2025/225

“Check-Before-you-Solve”: Verifiable Time-lock Puzzles

Jiajun Xin, The Hong Kong University of Science and Technology
Dimitrios Papadopoulos, The Hong Kong University of Science and Technology
Abstract

Time-lock puzzles are cryptographic primitives that guarantee to the generator that the puzzle cannot be solved in less than T sequential computation steps. They have recently found numerous applications, e.g., in fair contract signing and seal-bid auctions. However, solvers have no a priori guarantee about the solution they will reveal, e.g., about its ``usefulness'' within a certain application scenario. In this work, we propose verifiable time-lock puzzles (VTLPs) that address this by having the generator publish a succinct proof that the solution satisfies certain properties (without revealing anything else about it). Hence solvers are now motivated to ``commit'' resources into solving the puzzle. We propose VTLPs that support proving arbitrary NP relations about the puzzle solution. At a technical level, to overcome the performance hurdles of the ``naive'' approach of simply solving the puzzle within a SNARK that also checks , our scheme combines the ``classic'' RSA time-lock puzzle of Rivest, Shamir, and Wagner, with novel building blocks for ``offloading'' expensive modular group exponentiations and multiplications from the SNARK circuit. We then propose a second VTLP specifically for checking RSA-based signatures and verifiable random functions (VRFs). Our second scheme does not rely on a SNARK and can have several applications, e.g., in the context of distributed randomness generation. Along the road, we propose new constant-size proofs for modular exponent relations over hidden-order groups that may be of independent interest. Finally, we experimentally evaluate the performance of our schemes and report the findings and comparisons with prior approaches.

Note: This is the full version of our publication. We made minor modifications to the security definitions.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. IEEE Symposium on Security and Privacy (SP) '25
DOI
10.1109/SP61157.2025.00053
Keywords
Time-lock PuzzlesSNARKzero-knowledge
Contact author(s)
jxin @ cse ust hk
dipapado @ cse ust hk
History
2025-03-13: last of 2 revisions
2025-02-14: received
See all versions
Short URL
https://ia.cr/2025/225
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/225,
      author = {Jiajun Xin and Dimitrios Papadopoulos},
      title = {“Check-Before-you-Solve”: Verifiable Time-lock Puzzles},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/225},
      year = {2025},
      doi = {10.1109/SP61157.2025.00053},
      url = {https://eprint.iacr.org/2025/225}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.