1. Depth-Robust Graphs and Their Cumulative Memory Complexity
Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak
[View PDF on eprint.iacr.org]

@misc{cryptoeprint:2016:875,
author = {Joël Alwen and Jeremiah Blocki and Krzysztof Pietrzak},
title = {Depth-Robust Graphs and Their Cumulative Memory Complexity},
howpublished = {Cryptology ePrint Archive, Report 2016/875},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/875}},
}

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) Gn on n nodes. The quality of that iMHF is then captured by the following two pebbling complexities of Gn: \begin​{itemize} \item The parallel cumulative pebbling complexity Π∥cc(Gn) 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 Πst(Gn) should be as close as possible to Π∥cc(Gn) (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 Π∥cc(Gn)=Ω(n2/log(n)) (which matches a known upper bound) and Πst(Gn) is within a constant factor of Π∥cc(Gn).

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

Complementing these results, we provide new upper and lower bounds on the Π∥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 Π∥cc of the Password Hashing Competition winner Argon2i and one of the Balloon Hashing functions by O(n1.71). We also show an upper bound of O(n1.625) for the Catena functions and the two remaining Balloon Hashing functions.

1.