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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
kvenkata @ cs utexas edu
alewko @ cs columbia edu
bwaters @ cs utexas edu
History
2014-12-02: revised
2014-11-11: received
See all versions
Short URL
https://ia.cr/2014/925
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/925,
      author = {Venkata Koppula and Allison Bishop Lewko and Brent Waters},
      title = {Indistinguishability Obfuscation for Turing Machines with Unbounded Memory},
      howpublished = {Cryptology ePrint Archive, Paper 2014/925},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/925}},
      url = {https://eprint.iacr.org/2014/925}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.