"Check-Before-you-Solve": Verifiable Time-Lock Puzzles

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 $\mathcal{R}$ 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 $\mathcal{R}$, 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.