A Simple Construction of iO for Turing Machines
A Simple Construction of iO for Turing Machines
复制标题
图灵机 iO 的简单构建
DOI：
10.1007/978-3-030-03810-6_16
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Akshayaram Srinivasan
中科院分区：
文献类型：
--
作者：
Sanjam Garg;Akshayaram Srinivasan
我们给出了一个简单的结构的不可分割性混淆图灵机的时间混淆增长的描述大小的机器，否则，独立的运行时间和所使用的空间。虽然这个结果已经从电路和内射伪随机生成器的\（i\mathcal {O}\）中得知[Koppula，Lewko，and沃茨，STOC 2015]，但我们的构造和分析在概念上要简单得多。特别是，证明我们构造的主要技术组成部分是一个简单的组合卵石论证[Garg和Srinivasan，EUROPENTPT 2018]。我们的构造利用了电路和\（\mathrm {somewhere\，statistically\，binding\，hash\，functions}\）的不可混淆性混淆。
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}\).