A Simple Construction of iO for Turing Machines

Sanjam Garg and Akshayaram Srinivasan

Abstract

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.

Available format(s)
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2018
Contact author(s)
akshayaram @ berkeley edu
History
2018-09-28: revised
See all versions
Short URL
https://ia.cr/2018/771

CC BY

BibTeX

@misc{cryptoeprint:2018/771,
author = {Sanjam Garg and Akshayaram Srinivasan},
title = {A Simple Construction of iO for Turing Machines},
howpublished = {Cryptology ePrint Archive, Paper 2018/771},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/771}},
url = {https://eprint.iacr.org/2018/771}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.