CryptoDB
Time-Lock Puzzles with Efficient Batch Solving
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2024 |
| Abstract: | 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 \emph{batch-solve} puzzles, i.e., simultaneously open multiple puzzles while working to solve a \emph{single one}. Unfortunately, all previously known TLP constructions equipped for batch solving have been contingent upon super-polynomially secure indistinguishability obfuscation, rendering them impractical in real-world applications. In light of this challenge, we present novel TLP constructions that offer batch-solving capabilities without using heavy cryptographic hammers. Our proposed schemes are characterized by their simplicity in concept and efficiency in practice, 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 benefits from 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", wherein maliciously crafted puzzle instances may disrupt the batch-solving process of honest puzzles. In response, we demonstrate the construction of concrete and efficient TLPs designed to thwart such attacks. |
BibTeX
@inproceedings{eurocrypt-2024-33906,
title={Time-Lock Puzzles with Efficient Batch Solving},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-58723-8_11},
author={Jesko Dujmovic and Rachit Garg and Giulio Malavolta},
year=2024
}