IACR News item: 18 July 2014
Nir Bitansky, Ran Caentti, Yael Tauman-Kalai, Omer Paneth
ePrint ReportWe 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.
Additional news items may be found on the IACR news page.