CISPA
Browse

Time-Lock Puzzles with Efficient Batch Solving.

Download (840.05 kB)
preprint
posted on 2024-03-19, 10:52 authored by Jesko DujmovicJesko Dujmovic, Rachit Garg, Giulio Malavolta
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.

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

BibTeX

@misc{Dujmovic:Garg:Malavolta:2023, title = "Time-Lock Puzzles with Efficient Batch Solving.", author = "Dujmovic, Jesko" AND "Garg, Rachit" AND "Malavolta, Giulio", year = 2023, month = 10 }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC