Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
Venkata Koppula, Allison Bishop Lewko, Brent R. Waters · 2015
We show how to build indistinguishability obfuscation (iO) for Turing Machines where the overhead is polynomial in the security parameter λ, machine description |M| and input size |x| (with only a negligible correctness error). In particular, we avoid growing polynomially with the maximum space of a computation. Our construction is based on iO for circuits, one way functions and injective pseudo random generators.