Talk by Elaine Shi (Carnegie Mellon University)
summary
Claims a construction of quasi-linear EF iO that runs in time proportional to circuit size plus EF-proof size, assuming FHE, one-way functions and iO for polylog-size circuits, with security matching FHE (polynomial or sub-exponential). Replaces expensive BARG proofs with prefix-consistent SSB hashes to avoid quadratic blow-ups in padding and gate-by-gate checks, achieving only polylog blow-up. Builds quasi-linear multi-input FE and Turing-machine iO; proofs and costs are explicit.
AI-written summary · about
chapters (10)
- 0:00Efficient iO introduction
- 1:03Motivation for iO construction
- 3:12Theorem and security assumptions
- 8:56Challenges in efficient iO
- 13:22Applications of quasi-linear iO
- 20:54EF proofs in cryptography
- 23:08Padding for equivalence proofs
- 29:31iO for log-equivalent circuits
- 32:37SSB hashes with prefix consistency
- 36:42Summary and open questions
related talks
01h 01mCircularity Based IO, Part 1
52mIndistinguishability Obfuscation via Mathematical Proofs of Equivalence
31mHow to Construct Indistinguishability Obfuscation from Compact Functional Encryption
01h 03mLinear-Time Zero-Knowledge Arguments with Logarithmic Proof-Size
01h 04mTutorial on obfuscation
01h 05mObfuscation from Noisy Linear FE
01h 06mAn introduction to lattice-based folding schemes
58mObfuscation 2