We typically have seminars on Wednesday at noon in Malone 228. All seminar announcements will be sent to the theory mailing list.
Speaker: Amirbehshad Shahrasbi
Affiliation:Carnegie Mellon University
Speaker: Samson Zhou
Affiliation: Purdue University
Title: Password Hashing and Graph Pebbling
Abstract: Although the passwords of users are no longer being stored, we show an offline attacker is compelled to crack all stolen passwords under current security recommendations. Memory hard functions have been proposed as moderately expensive cryptographic tools for password hashing. The cryptanalysis of these functions has focused on the cumulative memory complexity and the energy complexity of the function. The first metric measures how much memory users must commit to evaluating a function, while the second metric measures how much energy users must commit. We prove these evaluations reduce to pebbling games on graphs but show that a tool for exact cryptanalysis of functions is unlikely to exist. Nevertheless, we provide asymptotic upper and lower bounds on several families of functions, including Argon2i, the winner of the password hashing competition that is currently being considered for standardization by the Cryptography Form Research Group of the Internet Research Task Force.
Joint work with Jeremiah Blocki, Ben Harsha, Ling Ren
Samson is a PhD candidate in the Department of Computer Science at Purdue University, under the supervision of Greg Frederickson and Elena Grigorescu. He received his undergraduate education at MIT, where he obtained a Bachelor’s in math and computer science, as well as a Master’s in computer science. He is a member of the Theory Group at Purdue and a winner of the Sigma Xi Research Awards Competition for graduate students in engineering. His current research interests are sublinear and approximation algorithms, with an emphasis on streaming algorithms.