Paper 2014/925

Indistinguishability Obfuscation for Turing Machines with Unbounded Memory

Venkata Koppula, Allison Bishop Lewko, and Brent Waters

Abstract

We show how to build indistinguishability obfuscation (iO) for Turing Machines where the overhead is polynomial in the security parameter lambda, 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. Our results are based on new ''selective enforcement'' techniques. Here we first create a primitive called positional accumulators that allows for a small commitment to a much larger storage. The commitment is unconditionally sound for a select piece of the storage. This primitive serves as an ''iO-friendly'' tool that allows us to make two different programs equivalent at different stages of a proof. The pieces of storage that are selected depend on what hybrid stage we are at in a proof. We first build up our enforcement ideas in a simpler context of ''message hiding encodings'' and work our way up to indistinguishability obfuscation.