The Memory Hardness of Scrypt

The Scrypt algorithm has been designed to be a sequential memory-hard function, i.e., the product of time and memory required to evaluate it should be large. Scrypt has found widespread applications in the context of password hashing (in fact, the same design methodology underlies Argon2d, one of the winning designs in the recent password-hashing competition).

However, providing an actual proof that Scrypt is indeed sequential memory-hard has been a challenging open problem. I will review the work initiated during the Simons program on providing provable guarantees for Scrypt.

Joint work with Joel Alwen, Binyi Chen, Chethan Kamath, Vladimir Kolmogorov, Krzysztof Pietrzak.