Crypto Seminar
— 5:30pm
Location:
In Person and Virtual - ET
-
Gates Hillman 8102 and Zoom
Speaker:
RACHIT GARG
,
Ph.D. Student, Department of Computer Science, The University of Texas at Austin
https://sites.google.com/view/rachit-garg/home
Time-Lock Puzzles with Efficient Batch Solving
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 that support 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.
Joint work with Jesko Dujmovic and Giulio Malavolta
Group Viewing and Zoom Participation. See announcement.
Event Website:
https://sites.google.com/view/crypto-seminar/home