Output-Compressing Randomized Encodings and Applications
summary
Defines compact (output-compressing) randomized encoding that encodes a Turing computation in time sublinear in its output and studies two securities, distributional indistinguishability security (weaker) and simulation security (impossible here). Shows impossibility for compact RE for general distributions under sub-exponential one‑way functions, gives a constructive CRS + functional encryption route that achieves compact or sublinear RE (and even simulation security in CRS), and builds a recursive tree+PRF encoding that converts one‑time RE into a reusable primitive and yields iO for bounded‑input machines.
AI-written summary · about
chapters (5)
- 0:00Start
- 2:07Simplicity of Randomized Encoding
- 18:15Compactness
- 38:21How about UNbounded-input TM?
- 45:12Conclusion
related talks
37mSuccinct Randomized Encodings from Laconic Function Evaluation, Faster and Simpler
01h 05mSuccinct Randomized Encodings from Lattices
01h 07mGarbled Circuits I
44mCoding Theory in Almost Linear Time and Sublinear Space
31mHow to Construct Indistinguishability Obfuscation from Compact Functional Encryption
01h 15mThe Journey Towards Program Obfuscation
12mAlgebraic Restriction Codes and their Applications
01h 01mDerandomization: A Quick Tutorial