Paper 2016/875
DepthRobust Graphs and Their Cumulative Memory Complexity
Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak
Abstract
Dataindependent 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 spacetime 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 depthrobustness (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.
Note: Upperbound for the complexity of Catena slightly weaker than in original version. Other than that only (lots of) cosmetic changes.
Metadata
 Available format(s)
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2017
 Keywords
 DataIndependent Memory Hard FunctionPassword HashingGraph PebblingCumulative Complexity
 Contact author(s)
 jalwen @ ist ac at
 History
 20170213: last of 2 revisions
 20160914: received
 See all versions
 Short URL
 https://ia.cr/2016/875
 License

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