International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Simple Construction of iO for Turing Machines

Authors:
Sanjam Garg
Akshayaram Srinivasan
Download:
DOI: 10.1007/978-3-030-03810-6_16
Search ePrint
Search Google
Conference: TCC 2018
Abstract: We give a simple construction of indistinguishability obfuscation 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 $$i\mathcal {O}$$ for circuits and injective pseudorandom generators, our construction and its analysis are conceptually much simpler. In particular, the main technical component in the proof of our construction is a simple combinatorial pebbling argument [Garg and Srinivasan, EUROCRYPT 2018]. Our construction makes use of indistinguishability obfuscation for circuits and $$\mathrm {somewhere\, statistically\, binding\, hash\, functions}$$ .
BibTeX
@inproceedings{tcc-2018-29018,
  title={A Simple Construction of iO for Turing Machines},
  booktitle={Theory of Cryptography},
  series={Theory of Cryptography},
  publisher={Springer},
  volume={11240},
  pages={425-454},
  doi={10.1007/978-3-030-03810-6_16},
  author={Sanjam Garg and Akshayaram Srinivasan},
  year=2018
}