Paper 2016/875

Depth-Robust Graphs and Their Cumulative Memory Complexity

Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak

Abstract

Data-independent Memory Hard Functions (iMHFS) are finding a growing number of applications in security; especially in the domain of password hashing. An important property of a concrete iMHF is specified by fixing a directed acyclic graph (DAG) $G_n$ on $n$ nodes. The quality of that iMHF is then captured by the following two pebbling complexities of $G_n$: \begin{itemize} \item The parallel cumulative pebbling complexity ${\mathrm{\Pi }}_{cc}^{\parallel }(G_n)$ must be as high as possible (to ensure that the amortized cost of computing the function on dedicated hardware is dominated by the cost of memory). \item The sequential space-time pebbling complexity $$ should be as close as possible to $$ (to ensure that using many cores in parallel and amortizing over many instances does not give much of an advantage). \end{itemize} In this paper we construct a family of DAGs with best possible parameters in an asymptotic sense, i.e., where $$ (which matches a known upper bound) and $$ is within a constant factor of $$. Our analysis relies on a new connection between the pebbling complexity of a DAG and its depth-robustness (DR) -- a well studied combinatorial property. We show that high DR is {\em sufficient} for high $$. Alwen and Blocki (CRYPTO'16) showed that high DR is {\em necessary} and so, together, these results fully characterize DAGs with high $$ in terms of DR. Complementing these results, we provide new upper and lower bounds on the $$ of several important candidate iMHFs from the literature. We give the first lower bounds on the memory hardness of the Catena and Balloon Hashing functions in a parallel model of computation and we give the first lower bounds of any kind for (a version) of Argon2i. Finally we describe a new class of pebbling attacks improving on those of Alwen and Blocki (CRYPTO'16). By instantiating these attacks we upperbound the $$ of the Password Hashing Competition winner Argon2i and one of the Balloon Hashing functions by $$. We also show an upper bound of $$ for the Catena functions and the two remaining Balloon Hashing functions.

Note: Upper-bound for the complexity of Catena slightly weaker than in original version. Other than that only (lots of) cosmetic changes.