Succinct Randomized Encodings from Laconic Function Evaluation, Faster and Simpler
summary
Claims construction under Circular LWE that yields succinct randomized encodings with encoding time roughly t^ε · s for any small constant ε<1, improving on prior ≈√t·s; construction uses a laconic function evaluation setup plus a garbled-circuit gadget chain to re-encrypt intermediate states, runs in ≈t^ε·s time assuming the setup is space-efficient, and bootstraps beyond √t at the cost of space/security tradeoffs; corollary: time-lock puzzles with arbitrary polynomial encoding/decoding gap.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 3:15Succinct RE definition
- 7:57Applications of succinct randomized encodings
- 10:08Faster encoding construction
- 13:25Laconic FE as building block
- 17:26From pre-processed to full succinct randomized encodings
- 23:07Garbled circuits role
- 26:44Security and efficiency
- 28:10Bootstrapping to ε-time
- 33:03Open problems
- 36:17Q&A
related talks
32mTime-Lock Puzzles from Randomized Encodings
44mCoding Theory in Almost Linear Time and Sublinear Space
48mOutput-Compressing Randomized Encodings and Applications
01h 07mGarbled Circuits I
01h 03mLockable Obfuscation
57mTutorial: Encrypted Computation from Lattices
44mObfuscation III
51mNew Ways to Garble Arithmetic Circuits