View article

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 (publiclyverifiable) delegation scheme for outsourcing PRAM computation, where the delegator’s runtime depends only on the program description and input/output size, and the server’s complexity matches the PRAM complexity of the computation up to polylogarithmic factors.