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, $\O$ is SIO for class $\C$ if $\O(C)\approx\O(C')$ whenever the pair $(C,C')$ is taken from a distribution over $\C$ where, for all $x$, $C(x)\neq C'(x)$ only with negligible probability.
We then show that an obfuscator is VGB for a class $\C$ if and only if it is SIO for $\C$. This result is unconditional and holds for any $\C$. 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$^1$, assuming that the underlying graded encoding scheme satisfies our variant of semantic security.
{\em Put together, we obtain VGB obfuscation for all NC$^1$ circuits under assumptions that are almost the same as those used by Pass et al. to obtain IO for NC$^1$ circuits.} We also show that semantic security is in essence {\em necessary} for showing VGB obfuscation.
Category / Keywords: Obfuscation, Multilinear Graded Encodings, Semantic Security, VBB, VGB Original Publication (with major differences): IACR-CRYPTO-2014 Date: received 15 Jul 2014, last revised 5 Aug 2014 Contact author: nirbitan at tau ac il Available format(s): PDF | BibTeX Citation Note: Noted that a preliminary version appears in the proceedings of crypto. Version: 20140805:181558 (All versions of this report) Short URL: ia.cr/2014/554 Discussion forum: Show discussion | Start new discussion