[Resource Topic] 2018/771: A Simple Construction of iO for Turing Machines

Welcome to the resource topic for 2018/771

A Simple Construction of iO for Turing Machines

Authors: Sanjam Garg, Akshayaram Srinivasan


We give a simple construction of indistinguishability obfus- cation for Turing machines where the time to obfuscate grows only with the description size of the machine and otherwise, independent of the running time and the space used. While this result is already known [Koppula, Lewko, and Waters, STOC 2015] from iO for circuits and injective pseudorandom generators, our construction and its analysis are conceptually much simpler. In particular, the main technical com- ponent in the proof of our construction is a simple combinatorial peb- bling argument [Garg and Srinivasan, EUROCRYPT 2018]. Our con- struction makes use of indistinguishability obfuscation for circuits and somewhere statistically binding hash functions.

ePrint: https://eprint.iacr.org/2018/771

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 .