Welcome to the resource topic for 2016/875
Title:
Depth-Robust Graphs and Their Cumulative Memory Complexity
Authors: Joël Alwen, Jeremiah Blocki, 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.
ePrint: https://eprint.iacr.org/2016/875
Talk: https://www.youtube.com/watch?v=K1BdGP2ffSI
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .