Title: Scrypt is optimally memory-hard
Abstract: Scrypt is a popular password-hashing and key-derivation algorithm (designed by Colin Percival in 2009) which is meant to be memory hard, i.e., the product of time and memory required to evaluate it must be as large as possible, even for parallel algorithms. Such memory requirements aim to make brute-force attacks by custom-made hardware significantly more expensive. The introduction of Scrypt has led to a growing interest in memory hardness, which was e.g. a de-facto requirement of the recent password-hashing competition. This interest has however also made it clear that memory hardness is a subtle target. To make things even worse, foundations to provide actual memory-hardness proofs have only recently started to emerge, and a gap still remains between practical designs and those that are provably memory hard. This talk will present our recent work showing that the Scrypt design itself (or more specifically, its core, called ROMix) is an optimally memory-hard function. This is the first example of a design which has been proved to achieve such degree of memory hardness. On the way, I will also briefly highlight the current state of research in provable memory hardness. This talk is based on joint work with Joel Alwen, Binyi Chen, Krzysztof Pietrzak, and Leonid Reyzin.