<div dir="ltr"><div style="font-size:12.8px"><span style="font-size:12.8px">Please join us for the next installment of the </span><a href="https://bostoncryptoday.wordpress.com/2015/04/09/friday-april-17-at-northeastern/" target="_blank" style="font-size:12.8px"><span class="">Charles</span> <span class="">River</span> Crypto Day</a><span style="font-size:12.8px"> this Friday, October 23 at MIT. </span></div><div style="font-size:12.8px"><span style="font-size:12.8px">See below for location info, updated schedule, and abstracts. </span><br></div><div style="font-size:12.8px"><span style="font-size:12.8px"><br></span></div><div style="font-size:12.8px"><span style="font-size:12.8px">This time we also plan to have a mini rump session after lunch of 1-3 talks, of 5-8 mins each. If you&#39;d like to give a talk at the rump session let us know. Preference will be given to students. </span></div><div style="font-size:12.8px"><span style="font-size:12.8px"><br></span></div><div style="font-size:12.8px">Looking forward to seeing you there,</div><div style="font-size:12.8px"><div style="font-size:12.8px">Yael, Vinod, Daniel, and Nir </div></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br style="font-size:12.8px"><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><span style="font-size:16px;line-height:normal">Location</span>: </b><b style="line-height:normal;font-family:&#39;Times New Roman&#39;;font-size:medium">MIT, Patil/Kiva Seminar Room, 32-G449 (<a href="http://www.na-mic.org/Wiki/index.php/Meeting_Locations:MIT_CSAIL_Star" target="_blank">directions</a>)</b></p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><span style="font-size:16px;line-height:normal"><b>Program:</b></span><br></p><table style="border:1px solid rgb(229,229,229);font-size:10px;outline:0px;padding:0px;vertical-align:baseline;border-collapse:collapse;border-spacing:0px;width:544px;color:rgb(0,0,0);font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><tbody style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><tr style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><td valign="top" width="105" style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px">9:30 – 10:00.</td><td style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px">Introduction/Coffee</td></tr><tr style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><td valign="top" style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px">10:00 – 11:00.</td><td style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px"><div style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5;background:transparent">Shai Halevi, IBM Research</div><div style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5;background:transparent"><strong style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">The State of Multi-linear Maps</strong></div></td></tr><tr style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><td valign="top" style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px">11:30 – 12:30.</td><td style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px">Eshan Chattopadhyay, University of Texas Austin<br><strong style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Non-Malleable Extractors and Codes, with their Many Tampered Extensions</strong></td></tr><tr style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><td valign="top" style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px">12:30 – 1:30.</td><td style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px">Lunch (provided)</td></tr></tbody></table><table style="border:1px solid rgb(229,229,229);font-size:10px;outline:0px;padding:0px;vertical-align:baseline;border-collapse:collapse;border-spacing:0px;width:544px;color:rgb(0,0,0);font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><tbody style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><tr style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><td valign="top" width="105" style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px">1:30 – 2:00.</td><td style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px">Rump Session</td></tr><tr style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><td valign="top" style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px">2:00 – 3:00.</td><td style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px"><div style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5;background:transparent"><span style="font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;line-height:normal">Ron Rothblum, MIT</span><br style="font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;line-height:normal"><strong style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;line-height:normal;background-image:initial;background-repeat:initial">Proofs and Arguments of Proximity: Verifying Computations in Sub-Linear Time</strong><br></div></td></tr><tr style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><td valign="top" style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px">3:30 – 4:30.</td><td style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px"><span style="font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif">abhi shelat, University of Virginia</span><br style="font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif"><strong style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">Impossibility and Difficulty in Constructing Obfuscation Schemes</strong></td></tr></tbody></table><h3 style="border:0px;margin:0px 0px 15px;font-size:16px;outline:0px;padding:0px;vertical-align:baseline;clear:both;color:rgb(0,0,0);font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">Abstracts:</h3><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Speaker: Shai Halevi</b></p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Title: The State of Cryptographic Multilinear Maps</b></p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">This talk will give an overview of current state of the constructions of and attacks against cryptographic multilinear maps.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"> </p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Speaker: Eshan Chattopadhyay</b></p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Title: Non-Malleable Extractors and Codes, with their Many Tampered Extensions</b></p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-malleable extractors, introduced by Dodis and Wichs; seedless non-malleable extractors, introduced by Cheraghchi and Guruswami; and non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs. Besides being interesting on their own, they also have important applications in cryptography. For example, seeded non-malleable extractors are closely related to privacy amplification with an active adversary, non-malleable codes are related to non-malleable secret sharing, and seedless non-malleable extractors provide a universal way to construct explicit non-malleable codes.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts. Indeed, the best known seeded non-malleable extractor requires min-entropy rate at least 0.49; while explicit constructions of non-malleable two-source extractors were not known even if both sources have full min-entropy, and was left as an open problem in the work of Cheraghchi-Guruswami. In addition, current constructions of non-malleable codes in the information theoretic setting only deal with the situation where the codeword is tampered once, and may not be enough for certain applications.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">In this paper we make progress towards solving the above problems. Our contributions are as follows.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">(1) We construct an explicit seeded non-malleable extractor for min-entropy <img src="https://s0.wp.com/latex.php?latex=k+%3E+%5Clog%5E2+n+&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="k &gt; \log^2 n " title="k &gt; \log^2 n " class="" width="71" height="18" style="border: none; margin: 0px 0px 10px; outline: 0px; padding: 0px; vertical-align: middle; height: auto; max-width: 545px; background: transparent;">. This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result by Li.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">(2) We construct the first explicit non-malleable two-source extractor for min-entropy <img src="https://s0.wp.com/latex.php?latex=k+%3E+n-n%5E%7B%5COmega%281%29%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="k &gt; n-n^{\Omega(1)} " title="k &gt; n-n^{\Omega(1)} " class="" width="94" height="15" style="border: none; margin: 0px 0px 10px; outline: 0px; padding: 0px; vertical-align: middle; height: auto; max-width: 545px; background: transparent;">, with output size <img src="https://s0.wp.com/latex.php?latex=n%5E%7B%5COmega%281%29%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="n^{\Omega(1)} " title="n^{\Omega(1)} " class="" width="33" height="15" style="border: none; margin: 0px 0px 10px; outline: 0px; padding: 0px; vertical-align: middle; height: auto; max-width: 545px; background: transparent;"> and error <img src="https://s0.wp.com/latex.php?latex=2%5E%7B-n%5E%7B%5COmega%281%29%7D%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="2^{-n^{\Omega(1)}} " title="2^{-n^{\Omega(1)}} " class="" width="43" height="17" style="border: none; margin: 0px 0px 10px; outline: 0px; padding: 0px; vertical-align: middle; height: auto; max-width: 545px; background: transparent;">.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">(3) We motivate and initiate the study of two natural generalizations of seedless non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times. For this, we construct the first explicit non-malleable two-source extractor with tampering degree t up to <img src="https://s0.wp.com/latex.php?latex=n%5E%7B%5COmega%281%29%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="n^{\Omega(1)} " title="n^{\Omega(1)} " class="" width="33" height="15" style="border: none; margin: 0px 0px 10px; outline: 0px; padding: 0px; vertical-align: middle; height: auto; max-width: 545px; background: transparent;">, which works for min-entropy <img src="https://s0.wp.com/latex.php?latex=k+%5Cgeq+n-n%5E%7B%5COmega%281%29%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="k \geq n-n^{\Omega(1)} " title="k \geq n-n^{\Omega(1)} " class="" width="94" height="18" style="border: none; margin: 0px 0px 10px; outline: 0px; padding: 0px; vertical-align: middle; height: auto; max-width: 545px; background: transparent;">, with output size <img src="https://s0.wp.com/latex.php?latex=n%5E%7B%5COmega%281%29%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="n^{\Omega(1)} " title="n^{\Omega(1)} " class="" width="33" height="15" style="border: none; margin: 0px 0px 10px; outline: 0px; padding: 0px; vertical-align: middle; height: auto; max-width: 545px; background: transparent;"> and error <img src="https://s0.wp.com/latex.php?latex=2%5E%7B-n%5E%7B%5COmega%281%29%7D%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="2^{-n^{\Omega(1)}} " title="2^{-n^{\Omega(1)}} " class="" width="43" height="17" style="border: none; margin: 0px 0px 10px; outline: 0px; padding: 0px; vertical-align: middle; height: auto; max-width: 545px; background: transparent;">.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">We further show that we can efficiently sample uniformly from any pre-image. By the connection in [CG14b], we also obtain the first explicit non-malleable codes with tampering degree t up to <img src="https://s0.wp.com/latex.php?latex=n%5E%7B%5COmega%281%29%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="n^{\Omega(1)} " title="n^{\Omega(1)} " class="" width="33" height="15" style="border: none; margin: 0px 0px 10px; outline: 0px; padding: 0px; vertical-align: middle; height: auto; max-width: 545px; background: transparent;">, relative rate <img src="https://s0.wp.com/latex.php?latex=n%5E%7B%5COmega%281%29%7D%2Fn+&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="n^{\Omega(1)}/n " title="n^{\Omega(1)}/n " class="" width="52" height="19" style="border: none; margin: 0px 0px 10px; outline: 0px; padding: 0px; vertical-align: middle; height: auto; max-width: 545px; background: transparent;">, and error <img src="https://s0.wp.com/latex.php?latex=2%5E%7B-n%5E%7B%5COmega%281%29%7D%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="2^{-n^{\Omega(1)}} " title="2^{-n^{\Omega(1)}} " class="" width="43" height="17" style="border: none; margin: 0px 0px 10px; outline: 0px; padding: 0px; vertical-align: middle; height: auto; max-width: 545px; background: transparent;">.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"> </p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Speaker: Ron Rothblum</b></p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Title: Proofs and Arguments of Proximity: Verifying Computations in Sub-Linear Time</b></p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">An interactive proof of proximity (IPP) is an interactive protocol in which a prover tries to convince a sublinear-time verifier that x \in L. Since the verifier runs in sublinear-time, following the property testing literature, the verifier is only required to reject inputs that are far from L. In a recent work, (Guy) Rothblum, Vadhan and Wigderson (STOC, 2013) constructed an IPP for every language computable by a low depth circuit.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">In this work we consider the computational analogue, where soundness is required to hold only against a computationally bounded cheating prover. We call such protocols interactive arguments of proximity.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">Assuming the existence of a sub-exponentially secure FHE scheme, we construct a one-round argument of proximity for every language computable in time t, where the running time of the verifier is o(n) + polylog(t) and the running time of the prover is poly(t).</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">As our second result, assuming sufficiently hard cryptographic PRGs, we give a lower bound, showing that the parameters obtained both in the IPPs of Rothblum et-al, and in our arguments of<br>proximity, are close to optimal.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">Based on joint work with Yael Kalai.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"> </p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Speaker: abhi shelat</b></p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Title: Impossibility and Difficulty in Constructing Obfuscation Schemes<br></b></p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">The golden standard for obfuscation, Virtual blackbox obfuscation, was shown to be impossible to achieve for general circuits in the standard model by the celebrated work of Barak et al (CRYPTO 2001). Recently, Brakerski and Rothblum (TCC’15), and Barak et al (Eurocrypt’14) overcome the impossibility and show how to achieve general-purpose VBB obfuscation by using an idealized-graded encoding scheme that enables performing \emph{high-degree} “zero-tests” on encodings.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">Building on a result of Canetti, Kalai and Paneth (TCC’15), we first show the impossibility of VBB obfuscation when the idealized-graded encoding scheme only allows evaluating constant-degree zero-tests on encodings. The main technique is to show how constant-degree zero-tests used in an obfuscation scheme can be “removed” by learning what the zero-tests would have answered, resulting in approximately-correct VBB obfuscation. This main technique also rules out sub-exponential secure VBB for general circuits when the idealized graded encoding scheme only allows evaluating degree n^\alpha zero-tests.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">We then apply the technique to indistinguishability obfuscation schemes and combine with well-known complexity results to show that constructing iO schemes from constant-degree graded encoding schemes in a blackbox way is as hard as basing public-key cryptography on one-way functions.</p><p style="border:0px;margin:0px 0px 15px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">This is joint work with Rafael Pass, and with Mohammad Mahmoody, Ameer Mohammed, and Soheil Nematihaji.</p></div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &quot;Charles River Crypto Day&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:charles-river-crypto-day+unsubscribe@googlegroups.com">charles-river-crypto-day+unsubscribe@googlegroups.com</a>.<br />
To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/charles-river-crypto-day/CACJEprPBm36fYjaG45QXA0qfqz3HfwRtwTUuQt37zc1%2BLUHW-Q%40mail.gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/charles-river-crypto-day/CACJEprPBm36fYjaG45QXA0qfqz3HfwRtwTUuQt37zc1%2BLUHW-Q%40mail.gmail.com</a>.<br />
For more options, visit <a href="https://groups.google.com/d/optout">https://groups.google.com/d/optout</a>.<br />