We bring the complexity of obfuscation down to the level of RAM programs. That is, assuming injective one way functions and indistinguishability obfuscators for all circuits, we construct indistinguishability obfuscators for RAM programs with the following parameters, up to polylogarithmic factors and a multiplicative factor in the security parameter: (a) The space used by the obfuscated program, as well as the initial size of the program itself, are proportional to the maximum space s used by the plaintext program on any input of the given size. (b) On each input, the runtime of the obfuscated program is proportional to s plus the runtime of the plaintext program on that input. The security loss is proportional to the number of potential inputs for the RAM program.
Our construction can be plugged into practically any existing use of indistinguishability obfuscation, such as delegation of computation, functional encryption, non-interactive zero-knowledge, and multi-party computation protocols, resulting in significant efficiency gains. It also gives the first succinct and efficient one-time garbled RAM scheme. The size of the garbled RAM is proportional to the maximum space $s$ used by the RAM machine, and its evaluation time is proportional to the running time of the RAM machine on plaintext inputs.
At the heart of our construction is a mechanism for succinctly obfuscating "iterated circuits", namely circuits that run in iterations, and where the output of an iteration is used as input to the next. As contributions of independent interest, we also introduce (a) a new cryptographic tool called Asymmetrically Constrained Encapsulation (ACE), that allows us to succinctly and asymmetrically puncture both the encapsulation and decapsulation keys; and (b) a new program analysis tool called Inductive Properties (IP), that allows us to argue about computations that are locally different, but yet globally the same.Category / Keywords: Obfuscation Date: received 30 Sep 2014 Contact author: holmgren at mit edu Available format(s): PDF | BibTeX Citation Version: 20140930:124723 (All versions of this report) Short URL: ia.cr/2014/769 Discussion forum: Show discussion | Start new discussion