<div dir="ltr"><div class="gmail_quote"><div dir="ltr"><div><div><br></div><div><div style="margin:0px;padding:0px;border:0px;font-family:Verdana,sans-serif;font-size:12px;line-height:20.3999996185303px;vertical-align:top;color:rgb(0,0,0)"><h1 style="margin:0px;padding:0px;border:0px;font-family:Arial,Helvetica,Verdana,sans-serif;font-size:17px;font-style:inherit;font-variant:inherit;line-height:21.8400001525879px;vertical-align:top;text-transform:uppercase">ON VIRTUAL GREY BOX OBFUSCATION FOR GENERAL CIRCUITS</h1></div><div style="margin:0px;padding:0px;border:0px;font-family:Verdana,sans-serif;font-size:12px;line-height:20.3999996185303px;vertical-align:top;color:rgb(0,0,0)"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0.5em 0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0.6em 0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><br></div></div></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><span style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top">Friday, October 17, 2014 - <span content="2014-10-17T10:30:00-04:00" style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top">10:30am</span> to <span content="2014-10-17T12:00:00-04:00" style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top">12:00pm</span></span></div></div></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left">Location: </div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top;float:left"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top">MIT (Stata Center, Hewlett room, 32-G882)</div></div></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left"><br></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left"><br></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left"><br></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left">Speaker: </div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top;float:left"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top">Nir Bitansky, MIT</div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><br></div></div></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left"><br></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left"><br></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left"><br></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left"><br></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left"> </div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left"><br></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:bold;line-height:inherit;vertical-align:top;float:left"> </div></div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><p style="margin:0.6em 0px 1.2em;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><strong style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;line-height:inherit;vertical-align:top"><br></strong></p><p style="margin:0.6em 0px 1.2em;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><strong style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;line-height:inherit;vertical-align:top">Abstract: </strong>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.<br><br>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&#39;)$ whenever the pair $(C,C&#39;)$ is taken from a distribution over $\C$ where, for all $x$, $C(x)\neq C&#39;(x)$ only with negligible probability.<br><br>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.<br><br>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.<br><br>{\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.</p><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"> </div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top">Joint work with Ran Canetti, Yael Tauman-Kalai, and Omer Paneth</div><div style="margin:0px;padding:0px;border:0px;font-family:inherit;font-size:inherit;font-style:inherit;font-variant:inherit;font-weight:inherit;line-height:inherit;vertical-align:top"><br></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>