<div dir="ltr"><div class="gmail_quote"><div dir="ltr"><div><p style="margin-bottom:15px;font-size:12px;line-height:1.5;outline:0px;color:rgb(0,0,0);font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial"><span style="line-height:1.5">Please join us tomorrow, </span><span style="line-height:1.5">Friday, February 20 </span><span style="line-height:1.5">for the next installment of </span><a href="https://bostoncryptoday.wordpress.com/" rel="nofollow" style="line-height:1.5" target="_blank">Crypto Day</a> <span style="line-height:1.5">at Microsoft Research, New England. The schedule and directions are below. Hope to see you there! </span></p><p style="margin-bottom:15px;font-size:12px;line-height:1.5;outline:0px;color:rgb(0,0,0);font-family:&#39;Helvetica Neue&#39;,Helvetica,Arial,sans-serif;background-image:initial;background-repeat:initial">Daniel, Vinod, Yael, Nir </p></div><blockquote class="gmail_quote" style="margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><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">Location and Arrival Instructions:</b><br>Microsoft New England Research and Development Center<br>One Memorial Drive, Cambridge MA 02142</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">Upon arrival, be prepared to show a picture ID and sign the Building Visitor Log when approaching the Lobby Floor Security Desk. Alert them to the name of the event, and ask them to direct you to the appropriate floor. The talks will be held the First Floor Conference Center, in the Horace Mann Conference Room. Detailed guidance on directions, via car or public transportation, is available <a href="http://research.microsoft.com/en-us/labs/newengland/visit.aspx" rel="nofollow" target="_blank">here</a>. Parking will be available for the on-site parking garage for $27/day.</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"><br></p><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">Program:</h3><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 style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px" valign="top" width="105">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 style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px" valign="top">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">Tal Malkin, Columbia</div><div style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5;background:transparent"><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">The Power of Negations in Cryptography</b></div></td></tr><tr style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><td style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px" valign="top">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">Rachel Lin, USCB<br><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Constant-Round Concurrent Zero-knowledge from Indistinguishability Obfuscation</b></td></tr><tr style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><td style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px" valign="top">12: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">Lunch (provided)</td></tr><tr style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><td style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px" valign="top">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">Alessandra Scaffuro, BU and Northeastern<br><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Garbled RAM From One-Way Functions</b></td></tr><tr style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent"><td style="border-top-width:1px;border-top-style:solid;border-top-color:rgb(229,229,229);font-size:12px;padding:6px 15px" valign="top">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">Henry Corrigan-Gibbs, Stanford<br><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Building Anonymous Messaging Systems that ‘Hide the Metadata’</b></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: Tal Malkin </b><br><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Title: The Power of Negations in Cryptography</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 study of monotonicity and negation complexity for Boolean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be monotone, and showed that one-way functions can be monotone (assuming they exist), but a pseudorandom generator cannot.</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 start by filling in the picture and proving that many other basic cryptographic primitives cannot be monotone. We then initiate a quantitative study of the power of negations, asking how many negations are required. We provide several lower bounds, some of them tight, for various cryptographic primitives and building blocks including one-way permutations, pseudorandom functions, small-bias generators, hard-core predicates, error-correcting codes, and randomness extractors. Among our results, we highlight the following.</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">i) Unlike one-way functions, one-way permutations cannot be monotone.</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">ii) We prove that pseudorandom functions require log n−O(1) negations (which is optimal up to the additive term).</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">iii) Error-correcting codes with optimal distance parameters require log n−O(1) negations (again, optimal up to the additive term).</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">iv) We prove a general result for monotone functions, showing a lower bound on the depth of any circuit with t negations on the bottom that computes a monotone function f in terms of the monotone circuit depth of f. This result addresses a question posed by Koroth and Sarma (2014) in the context of the circuit complexity of the Clique problem.</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">Joint work with Siyao Guo, Igor Carboni Oliveira, and Alon Rosen.</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: Rachel Lin </b><br><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Title: Constant-Round Concurrent Zero-knowledge from Indistinguishability Obfuscation</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">We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol relies on the existence of families of collision-resistant hash functions, one-way permutations, and indistinguishability obfuscators for P/poly (with slightly super-polynomial security).</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: Alessandra Scafuro</b> <br><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Title: Garbled RAM From One-Way Functions</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">Yao’s garbled circuit construction is a fundamental construction in cryptography and recent efficiency optimizations have brought it much closer to practice. However these constructions work only for circuits and garbling a RAM program involves the inefficient process of first converting it into a circuit. Towards avoiding this inefficiency, Lu and Ostrovsky [Eurocrypt 2013] introduced the notion of “garbled RAM” as a method to garble RAM programs directly. It can be seen as a RAM analogue of Yao’s garbled circuits such that, the size of the garbled program and the time it takes to create and evaluate it, is proportional only to the running time on the RAM program rather than its circuit size.<br>Known realizations of this primitive, either rely on stronger computational assumptions such as the existence of<br>Identity-Based Encryption, or rely on one-way functions only but do not achieve the aforementioned efficiency [Gentry, Halevi, Lu, Ostrovsky, Raykova and Wichs, EUROCRYPT 2014].</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 provide the first construction with strictly poly-logarithmic overhead in both space and time based only on the minimal assumption<br>that one-way functions exist.</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">Join work with Sanjam Garg, Steve Lu and Rafail Ostrovsky.</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: Henry Corrigan-Gibbs        </b><br><b style="border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;background:transparent">Title: Building Anonymous Messaging Systems that ‘Hide the Metadata’</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">Encryption can protect the contents of a message being sent over an open network. In many situations, though, hiding the contents of a communication is not enough: parties to a conversation want to conceal the fact that they ever communicated. In this talk, I will explain how anonymity-preserving messaging systems can help ‘hide the metadata’ pertaining to a conversation and I will survey the state of the art in anonymous messaging protocols.</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">A limitation of existing protocols is that they exhibit computation and communication costs that scale linearly with the number of users (i.e., the anonymity set size) or they require expensive zero-knowledge proofs. In recent work, we have designed Riposte, a new system for anonymous messaging that applies private-information-retrieval and secure multi-party computation techniques to circumvent these limitations.</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 implementation and experimental evaluation of Riposte demonstrates that, for latency-tolerant applications, the system can provide near-ideal anonymity for groups of millions of users—two orders of magnitude more than current systems support. I will conclude the talk with a discussion of open problems and directions for future work.</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">Joint work with: Dan Boneh and David Mazières</p></div><span class="HOEnZb"><font color="#888888">
</font></span></blockquote></div><span class="HOEnZb"><font color="#888888">

<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" target="_blank">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/81d26899-56ff-4c7a-81c5-76342744a13a%40googlegroups.com?utm_medium=email&amp;utm_source=footer" target="_blank">https://groups.google.com/d/msgid/charles-river-crypto-day/81d26899-56ff-4c7a-81c5-76342744a13a%40googlegroups.com</a>.<br>
For more options, visit <a href="https://groups.google.com/d/optout" target="_blank">https://groups.google.com/d/optout</a>.<br>
</font></span></div><br><br clear="all"><br>-- <br><div class="gmail_signature">Sharon Goldberg<br>Computer Science, Boston University<br><a href="http://www.cs.bu.edu/~goldbe" target="_blank">http://www.cs.bu.edu/~goldbe</a></div>
</div>