<div dir="ltr">Dear Cryptographers, <div><br></div><div> <span style="font-size:12.8px">Join us for the</span><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"> next <span class="m_6330089791060437892gmail-il">Charles</span> <span class="m_6330089791060437892gmail-il">River</span> <span class="m_6330089791060437892gmail-il">Crypto</span> <span class="m_6330089791060437892gmail-il"><wbr>Day</span> on Friday Dec 9 at Northeastern University</span></div><div><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"> </span></div><div><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"> See </span><font color="#000000" face="pt sans, sans-serif"><span style="font-size:12px"><a href="https://bostoncryptoday.wordpress.com/" target="_blank">https://bostoncryptoday.<wbr>wordpress.com/</a> </span></font><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"> or below for details.</span></div><div><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"><br></span></div><div><font color="#ff0000"><span style="font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"> Important: you must register</span><span style="font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"> to at</span></font><span style="color:rgb(255,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px">tend this event by filling out: </span><a href="https://docs.google.com/forms/d/e/1FAIpQLSc_hwEDG_G96-P7sRlnEHKwxl0WOqZYf7LvSN41n6i3iPyQHw/viewform" style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px;background-color:transparent;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border-width:0px 0px 1px;border-top-style:initial;border-right-style:initial;border-bottom-style:solid;border-left-style:initial;border-top-color:initial;border-right-color:initial;border-bottom-color:rgb(229,229,229);border-left-color:initial;margin:0px;outline:0px;padding:0px;vertical-align:baseline;text-decoration:none" target="_blank">this  form</a><span style="color:rgb(255,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px">. </span></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"><br></span></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"> See you all there! </span></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"><br></span></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"> best,</span></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"> Ron/Yael/Daniel/Vinod</span></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"><br></span></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px">-----------------------------</span></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;font-size:12px"><br></span></div><div style="font-size:12.8px"><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif"><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">When:</strong> Friday, December 9.</p><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif"><b style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Where: 90 <a href="https://www.google.com/maps/place/Snell+Library/@42.3390255,-71.0906102,16z/data=!4m5!3m4!1s0x0:0x46e17e056ed496c3!8m2!3d42.3383976!4d-71.0878347" style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border-width:0px 0px 1px;border-top-style:initial;border-right-style:initial;border-bottom-style:solid;border-left-style:initial;border-top-color:initial;border-right-color:initial;border-bottom-color:rgb(229,229,229);border-left-color:initial;margin:0px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);text-decoration:none" target="_blank">Snell Library</a>, Northreastern University Campus, Boston MA </b><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline"><br></strong></p><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif"><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Directions:</strong>  <a href="https://www.google.com/maps/place/Snell+Library/@42.3390255,-71.0906102,16z/data=!4m5!3m4!1s0x0:0x46e17e056ed496c3!8m2!3d42.3383976!4d-71.0878347" style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border-width:0px 0px 1px;border-top-style:initial;border-right-style:initial;border-bottom-style:solid;border-left-style:initial;border-top-color:initial;border-right-color:initial;border-bottom-color:rgb(229,229,229);border-left-color:initial;margin:0px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);text-decoration:none" target="_blank">This link</a> takes you to the correct building on google maps.  Also, see <a href="http://library.northeastern.edu/about/maps-and-directions/directions" style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border-width:0px 0px 1px;border-top-style:initial;border-right-style:initial;border-bottom-style:solid;border-left-style:initial;border-top-color:initial;border-right-color:initial;border-bottom-color:rgb(229,229,229);border-left-color:initial;margin:0px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);text-decoration:none" target="_blank">directions for public transportation and driving/parking</a>. Once you enter the library go downstairs to get to room 90.</p><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif"><span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(255,0,0)">Please register (free) to attend this event by filling out <a href="https://docs.google.com/forms/d/e/1FAIpQLSc_hwEDG_G96-P7sRlnEHKwxl0WOqZYf7LvSN41n6i3iPyQHw/viewform" style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border-width:0px 0px 1px;border-top-style:initial;border-right-style:initial;border-bottom-style:solid;border-left-style:initial;border-top-color:initial;border-right-color:initial;border-bottom-color:rgb(229,229,229);border-left-color:initial;margin:0px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);text-decoration:none" target="_blank">this  form</a>.<br>We need all attendees to register to get access to Snell library. </span></p><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif"><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Organizers:</strong> Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel Wichs.</p><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif"><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Thanks:</strong> <a href="http://www.bu.edu/macs/" style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border-width:0px 0px 1px;border-top-style:initial;border-right-style:initial;border-bottom-style:solid;border-left-style:initial;border-top-color:initial;border-right-color:initial;border-bottom-color:rgb(229,229,229);border-left-color:initial;margin:0px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);text-decoration:none" target="_blank">NSF MACS Project</a> for their generous support.</p></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><h3 style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:0px;margin:0px 0px 15px;font-size:16px;outline:0px;padding:0px;vertical-align:baseline;clear:both;color:rgb(0,0,0);font-weight:400;font-family:&quot;pt sans&quot;,sans-serif">Program:</h3><table width="675" style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:1px solid rgb(229,229,229);font-size:10px;outline:0px;padding:0px;vertical-align:baseline;border-collapse:collapse;width:544px;color:rgb(0,0,0);font-family:&quot;pt sans&quot;,sans-serif;height:419px"><tbody style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline"><tr style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline"><td valign="top" width="105" style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px">9:30 – 10:00.</td><td style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px">Introduction/Coffee</td></tr><tr style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline"><td valign="top" style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px">10:00 – 11:00.</td><td style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px"><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5">Dana Dachma-Soled, UMD</div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5"><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Towards Non-Black-Box Separations of Public Key Encryption and One Way Function</strong></div></td></tr><tr style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline"><td valign="top" style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px">11:15 – 12:15.</td><td style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px"><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5">Leo Reyzin, BU</div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5"><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5"><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Scrypt is Maximally Memory-Hard</strong></div></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5"></div></td></tr><tr style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline"><td valign="top" style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px">12:15– 1:30</td><td style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px">Lunch (provided)</td></tr><tr style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline"><td valign="top" style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px">1:30 – 2:30.</td><td style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px">Gillat Kol, Princeton<br><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Interactive Compression for Product Distributions</strong></td></tr><tr style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline"><td valign="top" style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px">3 – 4</td><td style="border-top:1px solid rgb(229,229,229);font-size:12px;padding:6px 15px">Mike Rosulek, Oregon State<br><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Linicrypt: A Model for Practical Cryptography<br><br></strong></td></tr></tbody></table><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><h3 style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:0px;margin:0px 0px 15px;font-size:16px;outline:0px;padding:0px;vertical-align:baseline;clear:both;color:rgb(0,0,0);font-weight:400;font-family:&quot;pt sans&quot;,sans-serif">Abstracts:</h3><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif"><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Speaker: <b style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Dana Dachman-Soled</b></strong><br><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Title: <strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Towards Non-Black-Box Separations of Public Key Encryption and One Way Function</strong></strong></p><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif">Abstract: Separating public key encryption from one way functions is one of the<br>fundamental goals of complexity-based cryptography. Beginning with the seminal<br>work of Impagliazzo and Rudich (STOC, 1989), a sequence of works have ruled<br>out certain classes of reductions from public key encryption (PKE)—or even<br>key agreement—to one way function. Unfortunately, known results—so called<br>black-box separations—do not apply to settings where the construction and/or<br>reduction are allowed to directly access the code, or circuit, of the one way<br>function. In this work, we present a meaningful, non-black-box separation<br>between public key encryption (PKE) and one way function.</p><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif">Specifically, we introduce the notion of BBN- reductions (similar to the BBNp<br>reductions of Baecher et al. (ASIACRYPT, 2013)), in which the construction E<br>accesses the underlying primitive in a black-box way, but wherein the<br>universal reduction R receives the efficient code/circuit of the underlying<br>primitive as input and is allowed oracle access to the adversary Adv. We<br>additionally require that the number of oracle queries made to Adv, and the<br>success probability of R are independent of the run-time/circuit size of the<br>underlying primitive. We prove that there is no non-adaptive, BBN- reduction<br>from PKE to one way function, under the assumption that certain types of<br>strong one way functions exist. Specifically, we assume that there exists a<br>regular one way function f such that there is no Arthur-Merlin protocol<br>proving that <code style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">z not in Range(f)&#39;&#39;, where soundness holds with high<br>probability over</code>no instances,” y ~ f(U_n), and Arthur may receive<br>polynomial-sized, non-uniform advice. This assumption is related to the<br>average-case analogue of the widely believed assumption coNP \not\subseteq<br>NP/poly.</p><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:0px;margin:0px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&quot;pt sans&quot;,sans-serif"></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:0px;margin:0px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&quot;pt sans&quot;,sans-serif"></div><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif"><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Speaker: Leo Reyzin</strong><br><strong style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Title: Scrypt is Maximally Memory-Hard</strong></p><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:0px;margin:0px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&quot;pt sans&quot;,sans-serif"></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:0px;margin:0px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&quot;pt sans&quot;,sans-serif"><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5">Abstract: The function scrypt (Percival, 2009) is defined as the result of n steps, where each step consists of selecting one or two previously computed w-bit values (the selection depends on the values themselves) and hashing them to get a new w-bit value. Because it is conjectured that this function is memory-hard, it has been used for key derivation and proofs of work in cryptocurrencies, and has inspired subsequent designs.</div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5"></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5">We show that indeed scrypt is maximally memory-hard in the parallel random oracle model. Specifically, we show that the product of memory and time used during the computation of scrypt must be Theta(n^2 w), even if the adversary is allowed to make an unlimited number of parallel random oracle queries at each step. Moreover, even if the amount of memory used fluctuates during the computation, we show that the sum of memory usage over time (a.k.a. “cumulative memory complexity” introduced by Alwen and Serbinenko at STOC 2015) is Theta(n^2 w), which implies high memory cost even for adversaries who can amortise the cost over many evaluations.</div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5"></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5">Our result improves both quantitatively and qualitatively upon the recent work by Alwen et al. (Eurocrypt ’16) who proved a weaker lower bound of Omega(n^2 w / log^2 n) for a restricted class of adversaries.  Our proof is the first showing optimal memory hardness in the random oracle model for any MHF.</div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5"></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5">Joint work with Joel Alwen, Binyi Chen, Krzysztof Pietrzak, and Stefano Tessaro, <a href="http://eprint.iacr.org/2016/989" style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline" target="_blank">http://eprint.iacr.<wbr>org/2016/989</a></div></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:0px;margin:0px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&quot;pt sans&quot;,sans-serif"></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:0px;margin:0px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&quot;pt sans&quot;,sans-serif"></div><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif"> </p><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif"><b style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Speaker: Gillat Kol</b><br><b style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Title: Interactive Compression for Product Distributions</b></p><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif">Abstract: In a profoundly influential 1948 paper, Claude Shannon introduced information theory and used it to study one-way data transmission problems over different channels, both noisy and noiseless. That paper initiated the study of error correcting codes and data compression, two concepts that are especially relevant today with the rise of the internet and data-intensive applications. In the last decades, interactive communication protocols are used and studied extensively, raising the fundamental question: To what extent can Shannon’s results be generalized to the interactive setting, where parties engage in an interactive communication protocol?</p><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif">In this talk we will focus on the interactive analog of data compression in an attempt to answer the above question. Specifically, we will consider the case where the parties have inputs that are independent of each other, and give a simulation protocol that communicates poly(I) bits, where I is the information cost of the original protocol. Our protocol is the first simulation protocol whose communication complexity is bounded by a polynomial in the information cost of the original protocol.</p><p style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;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:&quot;pt sans&quot;,sans-serif"><b style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Speaker: Mike Rosulek</b><br><b style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline">Title: Linicrypt: A Model for Practical Cryptography</b></p><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:0px;margin:0px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&quot;pt sans&quot;,sans-serif"><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5">Abstract: A wide variety of objectively practical cryptographic schemes can be constructed using only symmetric-key operations and linear operations. To formally study this restricted class of cryptographic algorithms, we present a new model called Linicrypt. A Linicrypt program has access to a random oracle whose inputs and outputs are field elements, and otherwise manipulates data only via fixed linear combinations.</div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5"></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5">Our main technical result is that it is possible to decide in polynomial time whether two given Linicrypt programs induce computationally indistinguishable distributions (against arbitrary PPT adversaries, in the random oracle model).</div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5"></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border:0px;margin:0px;outline:0px;padding:0px;vertical-align:baseline;line-height:1.5">We show also that indistinguishability of Linicrypt programs can be expressed as an existential formula, making the model amenable to automated program synthesis. In other words, it is possible to use a SAT/SMT solver to automatically generate Linicrypt programs that satisfy a given security constraint. Interestingly, the properties of Linicrypt imply that this synthesis approach is both sound and complete. We demonstrate this approach by synthesizing Linicrypt constructions of garbled circuits.</div></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:0px;margin:0px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&quot;pt sans&quot;,sans-serif"></div><div style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border:0px;margin:0px;font-size:12px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(0,0,0);line-height:1.5;font-family:&quot;pt sans&quot;,sans-serif">This talk is joint work with Brent Carmer.</div></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/CAHpnE7ZE%3DzLBUqy6uBoEh6JYra_EYu8b9XvLXMUKUVoRYjZfWA%40mail.gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/charles-river-crypto-day/CAHpnE7ZE%3DzLBUqy6uBoEh6JYra_EYu8b9XvLXMUKUVoRYjZfWA%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 />