Welcome to the resource topic for 2014/925
Title:
Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
Authors: Venkata Koppula, Allison Bishop Lewko, 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.
ePrint: https://eprint.iacr.org/2014/925
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .