[Busec] busec this week: Leo Reyzin (Wed 10am) NENS (Friday!)
goldbe at cs.bu.edu
Tue Oct 4 19:17:25 EDT 2016
A reminder for tomorrow'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.
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
BUsec Calendar: http://www.bu.edu/cs/busec/
The busec seminar gratefully acknowledges the support of BU's Center for
Reliable Information Systems and Cyber Security (RISCS).
On the Memory hardness of scrypt.
Speaker: Leo Reyzin (BU).
Wednesday October 7, 10am
Hariri Institute (111 Cummington St, Boston MA 02215)
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.
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. "cumulative memory complexity"
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.
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.
Joint work with Joel Alwen, Binyi Chen, Krzysztof Pietrzak, and Stefano
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Busec