Paper 2016/100
On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model
Joël Alwen, Binyi Chen, Chethan Kamath, Vladimir Kolmogorov, Krzysztof Pietrzak, and Stefano Tessaro
Abstract
We investigate lower bounds in terms of time and memory on the {\em parallel} complexity of an adversary $\cal A$ computing labels of randomly selected challenge nodes in direct acyclic graphs, where the $w$bit label of a node is the hash $H(.)$ (modelled as a random oracle with $w$bit output) of the labels of its parents. Specific instances of this general problem underlie both proofsofspace protocols [Dziembowski et al. CRYPTO'15] as well as memoryhardness proofs including {\sf scrypt}, a widely deployed password hashing and keyderivation function which is e.g. used within ProofsofWork for digital currencies like Litecoin. Current lower bound proofs for these problems only consider {\em restricted} algorithms $\cal A$ which perform only a single $H(.)$ query at a time and which only store individual labels (but not arbitrary functions thereof). This paper substantially improves this state of affairs; Our first set of results shows that even when allowing multiple parallel $\hash$ queries, the ``cumulative memory complexity'' (CMC), as recently considered by Alwen and Serbinenko [STOC '15], of ${\sf scrypt}$ is at least $w \cdot (n/\log(n))^2$, when ${\sf scrypt}$ invokes $H(.)$ $n$ times. Our lower bound holds for adversaries which can store (1) Arbitrary labels (i.e., random oracle outputs) and (2) Certain natural functions of these labels, e.g., linear combinations. The exact power of such adversaries is captured via the combinatorial abstraction of parallel ``entangled'' pebbling games on graphs, which we introduce and study. We introduce a combinatorial quantity $\gamma_n$ and under the conjecture that it is upper bounded by some constant, we show that the above lower bound on the CMC also holds for arbitrary algorithms $\cal A$, storing in particular arbitrary functions of their labels. We also show that under the same conjecture, the {\em 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 entangled pebbling on the same graph (given an initial $k$node pebbling). Under the conjecture, this solves the main open problem from the work of Dziembowski et al. In fact, we note that every nontrivial upper bound on $\gamma_n$ will lead to the first nontrivial bounds for general adversaries for this problem.
Note: Added a Section 0 summarising the current state of the conjectures from the paper.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2016
 Keywords
 memoryhard functionsScryptArgonpebblingproofs of space
 Contact author(s)
 krzpie @ gmail com
 History
 20160506: revised
 20160208: received
 See all versions
 Short URL
 https://ia.cr/2016/100
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/100, author = {Joël Alwen and Binyi Chen and Chethan Kamath and Vladimir Kolmogorov and Krzysztof Pietrzak and Stefano Tessaro}, title = {On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model}, howpublished = {Cryptology ePrint Archive, Paper 2016/100}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/100}}, url = {https://eprint.iacr.org/2016/100} }