conference paper
On the complexity of scrypt and proofs of space in the parallel random oracle model
LNCS
published
yes
Joel F
Alwen
author 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
Binyi
Chen
author
Chethan
Kamath Hosdurg
author 4BD3F30E-F248-11E8-B48F-1D18A9856A87
Vladimir
Kolmogorov
author 3D50B0BA-F248-11E8-B48F-1D18A9856A87
Krzysztof Z
Pietrzak
author 3E04A7AA-F248-11E8-B48F-1D18A9856A87
Stefano
Tessaro
author
KrPi
department
VlKo
department
EUROCRYPT: Theory and Applications of Cryptographic Techniques
Provable Security for Physical Cryptography
project
Discrete Optimization in Computer Vision: Theory and Practice
project
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).
Springer2016Vienna, Austria
eng
10.1007/978-3-662-49896-5_13
9666358 - 387
Alwen, Joel F, Binyi Chen, Chethan Kamath Hosdurg, Vladimir Kolmogorov, Krzysztof Z Pietrzak, and Stefano Tessaro. “On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model,” 9666:358–87. Springer, 2016. <a href="https://doi.org/10.1007/978-3-662-49896-5_13">https://doi.org/10.1007/978-3-662-49896-5_13</a>.
Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S. 2016. On the complexity of scrypt and proofs of space in the parallel random oracle model. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 9666. 358–387.
Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S. On the complexity of scrypt and proofs of space in the parallel random oracle model. In: Vol 9666. Springer; 2016:358-387. doi:<a href="https://doi.org/10.1007/978-3-662-49896-5_13">10.1007/978-3-662-49896-5_13</a>
Alwen, Joel F., et al. <i>On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model</i>. Vol. 9666, Springer, 2016, pp. 358–87, doi:<a href="https://doi.org/10.1007/978-3-662-49896-5_13">10.1007/978-3-662-49896-5_13</a>.
J. F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K. Z. Pietrzak, and S. Tessaro, “On the complexity of scrypt and proofs of space in the parallel random oracle model,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016, vol. 9666, pp. 358–387.
Alwen, J. F., Chen, B., Kamath Hosdurg, C., Kolmogorov, V., Pietrzak, K. Z., & Tessaro, S. (2016). On the complexity of scrypt and proofs of space in the parallel random oracle model (Vol. 9666, pp. 358–387). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria: Springer. <a href="https://doi.org/10.1007/978-3-662-49896-5_13">https://doi.org/10.1007/978-3-662-49896-5_13</a>
J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2016, pp. 358–387.
12312018-12-11T11:50:51Z2020-08-11T10:09:02Z