Paper Info
Title
Depth-Robust Graphs and Their Cumulative Memory Complexity.
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): -The parallel cumulative pebbling complexity. Pi(parallel to)(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). -The sequential space-time pebbling complexity Pi(st)(G(n)) should be as close as possible to. Pi(parallel to)(cc)(G(n)) (to ensure that using many cores in parallel and amortizing over many instances does not give much of an advantage). In this paper we construct a family of DAGs with best possible parameters in an asymptotic sense, i.e., where. Pi(parallel to)(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 to)(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 sufficient for high. Pi(parallel to)(cc). Alwen and Blocki (CRYPTO'16) showed that high DR is necessary and so, together, these results fully characterize DAGs with high Pi(parallel to)(cc) in terms of DR. Complementing these results, we provide new upper and lower bounds on the Pi(parallel to)(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 to)(cc) of the Password Hashing Competition winner Argon2i and one of the Balloon Hashing functions by O(n(1.71)). We also show an upper bound of O(n(1.625)) for the Catena functions and the two remaining Balloon Hashing functions.
Year
DOI
Venue
2017
10.1007/978-3-319-56617-7_1
ADVANCES IN CRYPTOLOGY - EUROCRYPT 2017, PT III
DocType
Volume
ISSN
Conference
10212
0302-9743
Citations 
PageRank 
References 
9
0.54
22
Authors
3
Name
Order
Citations
PageRank
Joel Alwen151622.21
Jeremiah Blocki223023.80
Krzysztof Pietrzak3151372.60