Paper 2014/554

On Virtual Grey Box Obfuscation for General Circuits

Nir Bitansky, Ran Canetti, Yael Tauman-Kalai, and Omer Paneth

Abstract

An obfuscator $\text{O}$ is Virtual Grey Box (VGB) for a class $\text{C}$ of circuits if, for any $C\in \text{C}$ and any predicate $\pi$, deducing $\pi (C)$ given $\text{O}(C)$ is tantamount to deducing $\pi (C)$ given unbounded computational resources and polynomially many oracle queries to $C$. VGB obfuscation is often significantly more meaningful than indistinguishability obfuscation (IO). In fact, for some circuit families of interest VGB is equivalent to full-fledged Virtual Black Box obfuscation. We investigate the feasibility of obtaining VGB obfuscation for general circuits. We first formulate a natural strengthening of IO, called {\em strong IO} (SIO). Essentially, $$ is SIO for class $$ if $$ whenever the pair $$ is taken from a distribution over $$ where, for all $$, $$ only with negligible probability. We then show that an obfuscator is VGB for a class $$ if and only if it is SIO for $$. This result is unconditional and holds for any $$. We also show that, for some circuit collections, SIO implies virtual black-box obfuscation. Finally, we formulate a slightly stronger variant of the semantic security property of graded encoding schemes [Pass-Seth-Telang Crypto 14], and show that existing obfuscators, such as the obfuscator of Barak et al. [Eurocrypt 14], are SIO for all circuits in NC$$, assuming that the underlying graded encoding scheme satisfies our variant of semantic security. {\em Put together, we obtain VGB obfuscation for all NC$$ circuits under assumptions that are almost the same as those used by Pass et al. to obtain IO for NC$$ circuits.} We also show that semantic security is in essence {\em necessary} for showing VGB obfuscation.

Note: Noted that a preliminary version appears in the proceedings of crypto.