Cryptology ePrint Archive: Report 2016/875

Depth-Robust Graphs and Their Cumulative Memory Complexity

JoŽl Alwen and 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 $\Pi^{\parallel}_{cc}(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 $\Pi_{st}(G_n)$ should be as close as possible to $\Pi^{\parallel}_{cc}(G_n)$ (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 $\Pi^{\parallel}_{cc}(G_n)=\Omega(n^2/\log(n))$ (which matches a known upper bound) and $\Pi_{st}(G_n)$ is within a constant factor of $\Pi^{\parallel}_{cc}(G_n)$.

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 $\Pi^{\parallel}_{cc}$. Alwen and Blocki (CRYPTO'16) showed that high DR is {\em necessary} and so, together, these results fully characterize DAGs with high $\Pi^{\parallel}_{cc}$ in terms of DR.

Complementing these results, we provide new upper and lower bounds on the $\Pi^{\parallel}_{cc}$ 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 $\Pi^{\parallel}_{cc}$ of the Password Hashing Competition winner Argon2i and one of the Balloon Hashing functions by $O\left(n^{1.71} \right)$. We also show an upper bound of $O(n^{1.625})$ for the Catena functions and the two remaining Balloon Hashing functions.

Category / Keywords: Data-Independent Memory Hard Function, Password Hashing, Graph Pebbling, Cumulative Complexity

Original Publication (with minor differences): IACR-EUROCRYPT-2017

Date: received 2 Sep 2016, last revised 13 Feb 2017

Contact author: jalwen at ist ac at

Available format(s): PDF | BibTeX Citation

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

Version: 20170213:203917 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]