Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
summary
Presents a construction that extends indistinguishability obfuscation from circuits to Turing machines with large tape by building a message-hiding encoding and an IO-friendly memory store that supports a small accumulator and selective enforcement of a single tape position. Proofs run a reverse-direction hybrid simulation, erase symbols backward, and need about T^2 hybrids; operations cost poly(λ, log T). Uses splittable signatures, avoids complexity leveraging, and yields a workable pathway to IO for unbounded-memory machines.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:17Aqua Skating Turing Machines
- 1:50Advantages for Using Obfuscation for Turing Machines
- 2:19Different Inputs Obfuscation
- 6:43Entire State Programming Approach
- 9:48Why the Memory Striction
- 19:04Prep Algorithm
- 19:18Update Accumulator
- 21:31How Selective Enforcement Works for the Proof
- 24:38Selective Enforcement
- 26:21Technical Summary
related talks
27mDifferentially Oblivious Turing Machines
21mWhen Obfuscations Preserve Cryptographic Constant-Time
21mWhen Oblivious is Not: Attacks against OPAM
33mYes, There is an Oblivious RAM Lower Bound!
26mAn Effective Approach to Software Obfuscation
57mSequential Information Flow
18mVerifying Indistinguishability of Privacy-Preserving Protocols
26mNon-Interference Preserving and Optimising Compilation with Hyperproperty Simulations