Time-Lock Puzzles from Randomized Encodings

on YouTube ↗32m

" summary

Construction produces time-lock puzzles by outputting a succinct randomized encoding of a tiny program that idles for T steps and then emits the message; solving the puzzle just runs the encoder’s public decoder for ~T steps. Security reduces to the existence of some non-parallelizing language: any shallow circuit that recovers the message yields a worst-case decider for that language. The cryptographic lever used is indistinguishability obfuscation (current way to build the encodings).

AI-written summary · about

" chapters (12)

1. 0:00Introduction
2. 0:20Time-lock encryption concept
3. 2:03Time-lock puzzle definition
4. 3:58Existing constructions
5. 7:20Challenges in construction
6. 10:27New approach overview
7. 11:57Randomized encodings
8. 15:22Construction of new puzzles
9. 19:23Complexity assumption
10. 22:05Proof intuition
11. 26:27Further results and models
12. 31:16Open problems and conclusion

" related talks

• 37mSuccinct Randomized Encodings from Laconic Function Evaluation, Faster and SimplerRachit Garg · Obfuscation
• 01h 05mSuccinct Randomized Encodings from LatticesGiulio Malavolta · Obfuscation
• 01h 03mLockable ObfuscationVenkata Koppula · Lattices: New Cryptographic Capabilities 2020
• 44mCoding Theory in Almost Linear Time and Sublinear SpaceDana Moshkovitz · Advances in the Theory of Error-Correcting Codes
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 01h 07mGarbled Circuits IBenny Applebaum · Cryptography Boot Camp 2015
• 45mNon-interactive Universal ArgumentsDana Shamir · Minimal Complexity Assumptions for Cryptography 2023
• 51mObfuscation via GGH15 Encodings, 10 Years LaterHoeteck Wee · Obfuscation