Author(s):

Alwen, Joël; Chen, Binyi; Kamath Hosdurg, Chethan; Kolmogorov, Vladimir N; Pietrzak, Krzysztof; Tessaro, Stefano

Title: 
On the complexity of scrypt and proofs of space in the parallel random oracle model

Title Series: 
LNCS

Affiliation 
IST Austria 
Abstract: 
We study the timeand memorycomplexities of the problem of computing labels of (multiple) randomly selected challengenodes in a directed acyclic graph. The wbit label of a node is the hash of the labels of its parents, and the hash function is modeled as a random oracle. Specific instances of this problem underlie both proofs of space [Dziembowski et al. CRYPTO’15] as well as popular memoryhard functions like scrypt. As our main tool, we introduce the new notion of a probabilistic parallel entangled pebbling game, a new type of combinatorial pebbling game on a graph, which is closely related to the labeling game on the same graph. As a first application of our framework, we prove that for scrypt, when the underlying hash function is invoked n times, the cumulative memory complexity (CMC) (a notion recently introduced by Alwen and Serbinenko (STOC’15) to capture amortized memoryhardness for parallel adversaries) is at least Ω(w · (n/ log(n))2). This bound holds for adversaries that can store many natural functions of the labels (e.g., linear combinations), but still not arbitrary functions thereof. We then introduce and study a combinatorial quantity, and show how a sufficiently small upper bound on it (which we conjecture) extends our CMC bound for scrypt to hold against arbitrary adversaries. We also show that such an upper bound solves the main open problem for proofsofspace protocols: namely, establishing that the time complexity of computing the label of a random node in a graph on n nodes (given an initial kwbit state) reduces tightly to the time complexity for black pebbling on the same graph (given an initial knode pebbling).

Keywords: 
Hash functions; Time complexity; Cryptography; Directed graphs; Random Oracle model; Arbitrary functions; Directed acyclic graph (DAG); Linear combinations; Memory complexity; Natural functions; Space protocols

Conference Title:

EUROCRYPT: Theory and Applications of Cryptographic Techniques

Volume: 
9666

Conference Dates:

May 8  12, 2016

Conference Location:

Vienna, Austria

Publisher:

Springer

Date Published:

20160101

Start Page: 
358

End Page:

387

URL: 

DOI: 
10.1007/9783662498965_13

Notes: 
Joël Alwen, Chethan Kamath, and Krzysztof Pietrzak’s research is partially supported by an ERC starting grant (259668PSPC). Vladimir Kolmogorov is partially supported by an ERC consolidator grant (616160DOICV). Binyi Chen was partially supported by NSF grants CNS1423566 and CNS1514526, and a gift from the Gareatis Foundation. Stefano Tessaro was partially supported by NSF grants CNS1423566, CNS1528178, a Hellman Fellowship, and the Glen and Susanne Culler Chair.
This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons Collaboration in Cryptography through NSF grant CNS1523467.

Open access: 
yes (repository) 