<div dir="ltr"><div class="gmail_quote"><div dir="ltr"><div class="gmail_quote"><div dir="ltr">Hi everyone,<br><br>A reminder for tomorrow&#39;s busec seminar by our own Leo Reyzin, who will tell us about his new research on memory-hard hash functions. Seminar is at the usual Wednesday 10am time, with lunch to follow.  </div><div dir="ltr"><br></div><div dir="ltr">Also, on Friday Oct 7, we are hosting the New England Networking and Systems day here at BU!  There is a great program along with a full session on security.</div><div dir="ltr"><br></div><div dir="ltr"><a href="http://systems.cs.brown.edu/nens/2016/" target="_blank">http://systems.cs.brown.edu/ne<wbr>ns/2016/</a><br></div><div dir="ltr"><br></div><div dir="ltr">Sharon<br><br>BUsec Calendar:  <a href="http://www.bu.edu/cs/busec/" target="_blank">http://www.bu.edu/cs/busec/</a><br><br>The busec seminar gratefully acknowledges the support of BU&#39;s Center for Reliable Information Systems and Cyber Security (RISCS). <br><br>******<br></div><div dir="ltr">On the Memory hardness of scrypt.<br></div><div>Speaker: Leo Reyzin (BU).</div><div>Wednesday October 7, 10am</div><div>Hariri Institute (111 Cummington St, Boston MA 02215)</div><div dir="ltr"><br></div><div dir="ltr"><div dir="ltr">The key derivation function scrypt (Percival, 2009) is defined as the result of n steps, where each step consists of selecting one or two previously computed values (the selection depends on the values themselves) and hashing them. It is conjectured that this function is memory-hard.</div><div dir="ltr"><br></div><div dir="ltr">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). 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. &quot;cumulative memory complexity&quot; introduced by Alwen and Serbinenko in 2015) is Theta(n^2). This suggests that computation of multiple instances of scrypt cannot be improved via amortization. Our result holds even if the adversary is allowed to make an unlimited number of parallel random oracle queries at each step.</div><div dir="ltr"><br></div><div dir="ltr">Previous work (Alwen, Chen, Kamath, Kolmogorov, Pietrzak, Tessaro 2016) showed a lowerbound of Omega( n^2 / log^2 n) on the memory complexity of scrypt in more restricted models, where the adversary was assumed to store only random oracle outputs or specific functions of them. Our result improves the bound quantitatively by eliminating the log^2 n factor and qualitatively by allowing arbitrary storage by the adversary.</div><div dir="ltr"><br></div><div dir="ltr">Joint work with Joel Alwen, Binyi Chen, Krzysztof Pietrzak, and Stefano Tessaro.</div></div></div>
</div>
</div><br>
<br></div>