CS graduate student Binyi Chen and Professor Stefano Tessaro received the "Best Paper Award" at EUROCRYPT 2017 in Paris, one of the two top-tier yearly conferences in cryptography devoted to all aspects of cryptology. 

Their paper, titled “Scrypt is Maximally Memory-Hard,” is joint work with the cryptography group at IST Austria, and Leonid Reyzin at Boston University. Binyi Chen also delivered the presentation of the paper at the conference. Their work addresses an important question in password security. In secure systems, passwords are usually not stored directly in the clear. Rather, they are first processed by a special cryptographic algorithm -- a so-called “hash function” -- and the resulting output or “password hash” is stored instead. To authenticate a user, the password hash can be recomputed from the password. However, it is hard to recover the password from the hash. Therefore, an attacker that steals the password hashes can only recover the password by re-computing the hash for several password guesses, until the right one eventually is found. While this process is seemingly very expensive, specialized hardware can allow an attacker to process billions of passwords per second. This is a serious concern, as theft of hashed passwords has become fairly common (e.g., in the recent Yahoo hack).

Chen's and Tessaro’s work deals with a specific hash function, called Scrypt, designed for secure password hashing. The work proves that Scrypt meets the desired security requirement of being a so-called memory-hard function, i.e., a function whose evaluation requires a large amount of memory to be evaluated reasonably fast. This is an important property, as it substantially increases the cost of password cracking, and reduces the benefits of custom-made hardware. For similar reasons, Scrypt has also been used within so-called proof-of-work schemes that underlie cryptocurrencies, in particular Litecoin.

While Scrypt was proposed in 2009 by Colin Percival, a proof that it is memory-hard has been an open problem for several years. Therefore, the work by Tessaro, Chen, and co-authors provides an important validation for the usage of Scrypt in practice; but also has important theoretical ramifications, as Scrypt is the first example of an algorithm which has been proved to achieve optimal memory hardness.

Read the abstract here.
 

About EUROCRYPT 
Eurocrypt 2017 is one of the three flagship conferences of the International Association for Cryptologic Research (IACR), and is organized by the Crypto Group at ENS Paris.  This year marked the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques.