Computation-Trace Indistinguishability Obfuscation and its Applications.
Yu‐Chi Chen, Sherman S. M. Chow, Kai-Min Chung, Russell W. F. Lai, Wei-Kai Lin, Hong-Sheng Zhou · 2015
We introduce a new, instance-based notion of indistinguishability obfuscation, called computation-trace indistinguishability obfuscation (CiO), for (parallel) RAM computation. CiO only obfuscates a fixed, single computation instance, as opposed to iO which obfuscates a function on all input instances. Specifically, for Π defined by (P, x) consisting of a (parallel) RAM program P and an input x, the obfuscations of two instances Π and Π ′ are required to be indistinguishable only when the execution of Π and Π ′ generate an identical computation trace; namely, identical sequences of CPU states and memory content. On the other hand, we require the obfuscation to be (i) fully succinct: the runtime of the obfuscator (and thus the size of the obfuscated instance) depends only on the description and input/output size of Π, but is independent of the time and space complexities of Π, and (ii) efficiency preserving: the obfuscated instance is a (parallel) RAM program that preserves parallel/total time and space complexities of Π up to polylogarithmic factors. As our main results, we construct CiO for parallel RAM (PRAM) computation based on iO for circuits and one-way functions, and demonstrate the power of CiO by the following applications. • With digital signatures, our CiO for PRAM immediately implies the first two-message (publicly-verifiable) delegation scheme for outsourcing PRAM computation, where the delegator’s runtime de-