Professor Leo Reyzin Wins Best Paper Award at Eurocrypt 2017
Leo Reyzin, together with collaborators at IST Austria and UC Santa Barbara, received a Best Paper Award from the Eurocrypt 2017 conference for his work “Scrypt is Maximally Memory-Hard.” (http://eprint.iacr.org/2016/989)
The paper solves a problem that has been open since 2009: does there exist a function with maximal memory hardness? A function is memory-hard if any algorithm used to compute it, no matter how clever, must use a lot of memory for a sustained period of time. Such functions are valuable for securing passwords, because they increase the cost of a brute-force password-cracking attack, requiring the adversary to use a lot of memory in order to search for the correct password. They are also used as proofs of work for cryptocurrencies, because they help level the playing field for different types of miners—no matter what custom hardware the miner uses to reduce the cost of computation, the miner must spend money on memory.
The first attempt at a memory-hard function, called scrypt, was made by Percival in 2009. Percival conjectured that it was memory-hard, but no proof of this conjecture was known. Since then, some other, more complex, functions have been proposed and proven memory-hard, but no proposal achieved maximal memory hardness. All proposals, including scrypt, rely on the assumption that a certain building block—known as a cryptographic hash function—is random.
Reyzin’s result, obtained jointly with Joël Alwen, Binyi Chen, Krzysztof Pietrzak, and Stefano Tessaro during Reyzin’s sabbatical visit to IST Austria, shows not only that this first conjectured memory-hard function is indeed memory-hard, but also that it is as memory-hard as possible, up to a small constant factor.