---
res:
bibo_abstract:
- 'We study the time-and memory-complexities of the problem of computing labels
of (multiple) randomly selected challenge-nodes in a directed acyclic graph. The
w-bit 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 memory-hard
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 memory-hardness
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 proofs-of-space protocols: namely, establishing that the time complexity of
computing the label of a random node in a graph on n nodes (given an initial kw-bit
state) reduces tightly to the time complexity for black pebbling on the same graph
(given an initial k-node pebbling).@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Joel F
foaf_name: Alwen, Joel F
foaf_surname: Alwen
foaf_workInfoHomepage: http://www.librecat.org/personId=2A8DFA8C-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Binyi
foaf_name: Chen, Binyi
foaf_surname: Chen
- foaf_Person:
foaf_givenName: Chethan
foaf_name: Kamath Hosdurg, Chethan
foaf_surname: Kamath Hosdurg
foaf_workInfoHomepage: http://www.librecat.org/personId=4BD3F30E-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Vladimir
foaf_name: Kolmogorov, Vladimir
foaf_surname: Kolmogorov
foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Pietrzak, Krzysztof Z
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9139-1654
- foaf_Person:
foaf_givenName: Stefano
foaf_name: Tessaro, Stefano
foaf_surname: Tessaro
bibo_doi: 10.1007/978-3-662-49896-5_13
bibo_volume: 9666
dct_date: 2016^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: On the complexity of scrypt and proofs of space in the parallel random
oracle model@
...