Obfuscation with Constant Multiplicative Size Overhead
summary
Claims a construction of indistinguishability obfuscation for Turing machines whose obfuscated size is constant multiplicative overhead — essentially 2× size overhead plus poly(security, L) — assuming iO for circuits. Core tools are randomized encodings, PRF-driven randomness, positional IO and a new primitive called Oblivious Evaluation encodings with input/bit puncturing helpers. Proof uses hybrid switches and bit-puncturing to move computation from M0 to M1; result is a theoretical scheme with a security reduction, not an implementation demonstration.
AI-written summary · about
chapters (11)
- 0:00Introduction and motivation
- 2:01Background on obfuscation
- 3:28Defining succinct IO
- 6:16Efficiency and constructions
- 8:56Main result and corollaries
- 12:46Oblivious evaluation encoding
- 16:00OE helper algorithms
- 18:53Building succinct IO from OE
- 20:51High-level security proof
- 22:34Constructing OE
- 26:26Decomposability and reuse
related talks
27mDifferentially Oblivious Turing Machines
21mWhen Obfuscations Preserve Cryptographic Constant-Time
26mAn Effective Approach to Software Obfuscation
21mWhen Oblivious is Not: Attacks against OPAM
33mYes, There is an Oblivious RAM Lower Bound!
44mIOP based Zero-Knowledge Proofs
01h 06mOn the Assumptions Used for Obfuscation
28mProving Obliviousness of Probabilistic Algorithms with Formal Verification