Depth-robust graphs and their cumulative memory complexity Conference Paper

Author(s): Alwen, Joël; Blocki, Jeremiah; Pietrzak, Krzysztof
Title: Depth-robust graphs and their cumulative memory complexity
Title Series: LNCS
Affiliation IST Austria
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: 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). 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). 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 sufficient for high Π∥cc. Alwen and Blocki (CRYPTO’16) showed that high DR is 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.
Conference Title: EUROCRYPT: Theory and Applications of Cryptographic Techniques
Volume: 10212
Conference Dates: April 30 - May 4, 2017
Conference Location: Paris, France
ISBN: 978-331956616-0
Publisher: Springer  
Date Published: 2017-04-01
Start Page: 3
End Page: 32
Sponsor: The first and third authors were supported by the European Research Council, ERC consolidator grant (682815 - TOCNeT).
DOI: 10.1007/978-3-319-56617-7_1
Open access: yes (repository)
IST Austria Authors
  1. Joel Alwen
    13 Alwen
Related IST Austria Work