International Association
for Cryptologic Research

A key source of inefficiency in existing obfuscation schemes is that they operate on programs represented as Boolean circuits

or (with stronger assumptions and costlier constructs) as Turing machines.

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.