Name
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 $$\\texttt {scrypt} $$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 $$\\varOmega w \\cdot n/\\log n^2$$Ωw﾿n/logn2. 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 $$\\texttt {scrypt} $$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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-662-49896-5_13 | IACR Cryptology ePrint Archive |
Field | DocType | Volume |
Discrete mathematics,Linear combination,Combinatorics,Open problem,Upper and lower bounds,Computer science,Random oracle,Directed acyclic graph,Hash function,Time complexity,Conjecture | Journal | 2016 |
ISSN | Citations | PageRank |
0302-9743 | 11 | 0.58 |
References | Authors | |
8 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joel Alwen | 1 | 516 | 22.21 |
| Binyi Chen | 2 | 35 | 1.61 |
| Chethan Kamath | 3 | 23 | 5.50 |
| Vladimir Kolmogorov | 4 | 10067 | 611.11 |
| Krzysztof Pietrzak | 5 | 1513 | 72.60 |
| Stefano Tessaro | 6 | 599 | 38.30 |