Speaker:
Jeremiah Blocki

Abstract:
A secure password hashing algorithm should have the properties that (1) it can be computed quickly (e.g., at most one second) on a personal computer, (2) it is prohibitively expensive for an attacker to compute the function millions or billions of times to crack the user's password even if the attacker uses customized hardware. The first property ensures that the password hashing algorithm does not introduce an intolerably long delay for the user during authentication, and the second property ensures that an offline attacker will fail to crack most user passwords. Memory hard functions (MHFs), functions whose computation require a large amount of memory, are a promising cryptographic primitive to enable the design of a password hashing algorithm achieving both goals.

Graph pebbling is a powerful abstraction which is used to analyze the (in)security of data-independent MHFs (iMHFs) --- a special class of MHFs that provide natural resistance to side-channel attacks. In the parallel random oracle model we can prove that the cumulative memory complexity of an iMHF f_G is directly tied to pebbling cost of the underlying data-dependence graph G. In this talk we look at the extractor arguments which allow us to establish this fundamental connection between graph pebbling and cumulative memory complexity. Intuitively, we show that if an algorithm A evaluating f_G has small cumulative memory cost (below the pebbling cost of G) then we can derive a contradiction by building an extractor E which uses A to ``compress" the random oracle. We will conclude the talk by discussing several open problems e.g., is it possible to extend the extractor argument to the quantum random oracle model?