CS Professor Leo Reyzin wins Best Paper at Eurocrypt 2017

Computer Science professor, Leo Reyzin, has won Best Paper at the Eurocrypt 2017 conference for his work, “Scrypt is Maximally Memory-Hard.” The paper, which was written by Reyzin and collaborators, Joël Alwen, Binyi Chen, Krzysztof Pietrzak, and Stefano Tessaro, discusses their work on memory-hard function.

Eurocrypt is an international conference on the the theory and application of cryptographic techniques. Held from April 30-May 4 this year in Paris, thousands of cryptography researchers around the world joined forces to discuss the future of the science, including topics on encryption, using secure computational methods, and multi-party networks.

Reyzin’s 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. 

Reyzin and his collaborators’ result, done during a 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. The paper was presented by Binyi Chen. It was also presented last December by Reyzin at the Charles River Crypto Day — an event co-sponsored by the Hariri Institute and BU’s Center for Center for Reliable Information Systems and Cyber Security (RISCS).