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) 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 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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Keywords
Data-Independent Memory Hard FunctionPassword HashingGraph PebblingCumulative Complexity
Contact author(s)
jalwen @ ist ac at
History
2017-02-13: last of 2 revisions
2016-09-14: received
See all versions
Short URL
https://ia.cr/2016/875
License
Creative Commons Attribution
CC BY

BibTeX

@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, Paper 2016/875},
      year = {2016},
      url = {https://eprint.iacr.org/2016/875}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.