[Busec] MIT CIS Seminar tomorrow 10/17: Nir Bitansky

Leonid Reyzin reyzin at cs.bu.edu
Thu Oct 16 12:31:37 EDT 2014


Friday, October 17, 2014 - 10:30am to 12:00pm
MIT (Stata Center, Hewlett room, 32-G882)

Nir Bitansky, MIT

*Abstract: *An obfuscator $\O$ is Virtual Grey Box (VGB) for a class $\C$
of circuits if, for any $C \in \C$ and any predicate $\pi$, deducing
$\pi(C)$ given $\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, $\O$ is SIO for class $\C$ if $\O(C)$ is
computationally indistinguishable from $\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

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

{\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.

Joint work with Ran Canetti, Yael Tauman-Kalai, and Omer Paneth
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20141016/02153b09/attachment.html>

More information about the Busec mailing list