“Check-Before-you-Solve”: Verifiable Time-lock Puzzles
发表信息
- 原文链接暂无
- archive
作者
笔记
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 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 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.
Note: This is the full version of our publication. We made minor modifications to the security definitions.