{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:47Z","timestamp":1766281007518},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319566160"},{"type":"electronic","value":"9783319566177"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-56617-7_1","type":"book-chapter","created":{"date-parts":[[2017,3,30]],"date-time":"2017-03-30T22:33:34Z","timestamp":1490913214000},"page":"3-32","source":"Crossref","is-referenced-by-count":33,"title":["Depth-Robust Graphs and Their Cumulative Memory Complexity"],"prefix":"10.1007","author":[{"given":"Jo\u00ebl","family":"Alwen","sequence":"first","affiliation":[]},{"given":"Jeremiah","family":"Blocki","sequence":"additional","affiliation":[]},{"given":"Krzysztof","family":"Pietrzak","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,4,1]]},"reference":[{"key":"1_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/978-3-662-53008-5_9","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"J Alwen","year":"2016","unstructured":"Alwen, J., Blocki, J.: Efficiently computing data-independent memory-hard functions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 241\u2013271. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-53008-5_9"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Alwen, J., Blocki, J.: Towards practical attacks on Argon2i and balloon hashing. In: Proceedings of the 2nd IEEE European Symposium on Security and Privacy (EuroS&P 2017). IEEE (2017, to appear). http:\/\/eprint.iacr.org\/2016\/759","DOI":"10.1109\/EuroSP.2017.47"},{"key":"1_CR3","unstructured":"Abadi, M., Burrows, M., Wobber, T.: Moderately hard, memory-bound functions. In: Proceedings of the Network and Distributed System Security Symposium, NDSS, San Diego, California, USA (2003)"},{"key":"1_CR4","unstructured":"Alwen, J., Chen, B., Kamath, C., Kolmogorov, V., Pietrzak, K., Tessaro, S.: On the complexity of RYPT and proofs of space in the parallel random oracle model. In: Advances in Cryptology - EUROCRYPT 2016 - Vienna, Austria, May 8\u201312, 2016, Part II, pp. 358\u2013387 (2016). http:\/\/eprint.iacr.org\/2016\/100"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Alwen, J., Chen, B., Pietrzak, K., Reyzin, L., Tessaro, S.: RYPT is Maximally Memory-Hard. In: Advances in Cryptology-EUROCRYPT 2017. Springer (2017, to appear). http:\/\/eprint.iacr.org\/2016\/989","DOI":"10.1007\/978-3-319-56617-7_2"},{"key":"1_CR6","unstructured":"Alwen, J., Gai, P., Kamath, C., Klein, K., Osang, G., Pietrzak, K., Reyzin, L., Rolnek, M., Rybr. M.: On the memory-hardness of data-independent password-hashing functions. Cryptology ePrint Archive, Report 2016\/783 (2016). http:\/\/eprint.iacr.org\/2016\/783"},{"key":"1_CR7","unstructured":"Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC 2015 (2015). http:\/\/eprint.iacr.org\/2014\/238"},{"key":"1_CR8","unstructured":"Boneh, D., Corrigan-Gibbs, H., Schechter, S.: Balloon hashing: provably space-hard hash functions with data-independent access patterns. Cryptology ePrint Archive, Report 2016\/027, Version: 20160601:225540 (2016). http:\/\/eprint.iacr.org\/"},{"key":"1_CR9","unstructured":"Biryukov, A., Dinu, D., Khovratovich, D.: Fast and tradeoff-resilient memory-hard functions for cryptocurrencies and password hashing. Cryptology ePrint Archive, Report 2015\/430 (2015). http:\/\/eprint.iacr.org\/2015\/430"},{"key":"1_CR10","unstructured":"Biryukov, A., Dinu, D., Khovratovich, D.: Argon2 password hash. Version 1.3 (2016). https:\/\/www.cryptolux.org\/images\/0\/0d\/Argon2.pdf"},{"key":"1_CR11","unstructured":"Biryukov, A., Dinu, D., Khovratovich, D., Josefsson, S.: The memory-hard Argon2 password hash and proof-of-work function. Internet-Draft draft-irtf-cfrg-argon2-00, Internet Engineering Task Force, March 2016"},{"key":"1_CR12","unstructured":"Biryukov, A., Khovratovich, D.: Tradeoff cryptanalysis of memory-hard functions. Cryptology ePrint Archive, Report 2015\/227 (2015). http:\/\/eprint.iacr.org\/"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Chandra, A.K.: Efficient compilation of linear recursive programs. In: SWAT (FOCS), pp. 16\u201325. IEEE Computer Society (1973)","DOI":"10.1109\/SWAT.1973.7"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: An observation on time-storage trade off. In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC 1973, pp. 29\u201333. ACM, New York (1973)","DOI":"10.1145\/800125.804032"},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/978-3-662-48000-7_29","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"S Dziembowski","year":"2015","unstructured":"Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs of space. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 585\u2013605. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48000-7_29"},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/978-3-540-45146-4_25","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"C Dwork","year":"2003","unstructured":"Dwork, C., Goldberg, A., Naor, M.: On memory-bound functions for fighting spam. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 426\u2013444. Springer, Heidelberg (2003). doi: 10.1007\/978-3-540-45146-4_25"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-642-22792-9_19","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"S Dziembowski","year":"2011","unstructured":"Dziembowski, S., Kazana, T., Wichs, D.: Key-evolution schemes resilient to space-bounded leakage. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 335\u2013353. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-22792-9_19"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-642-19571-6_9","volume-title":"Theory of Cryptography","author":"S Dziembowski","year":"2011","unstructured":"Dziembowski, S., Kazana, T., Wichs, D.: One-time computable self-erasing functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 125\u2013143. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-19571-6_9"},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/11535218_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"C Dwork","year":"2005","unstructured":"Dwork, C., Naor, M., Wee, H.: Pebbling and proofs of work. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 37\u201354. Springer, Heidelberg (2005). doi: 10.1007\/11535218_3"},{"key":"1_CR20","unstructured":"Paul, E., Graham, R.L., Szemeredi, E.: On sparse graphs with dense long paths. Technical report, Stanford, CA, USA (1975)"},{"key":"1_CR21","unstructured":"Christian, F., Stefan, L., Jakob, W.: Catena: a memory-consuming password scrambler. IACR Cryptology ePrint Archive 2013, 525 (2013)"},{"key":"1_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-662-53015-3_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"B Hemenway","year":"2016","unstructured":"Hemenway, B., Jafargholi, Z., Ostrovsky, R., Scafuro, A., Wichs, D.: Adaptively secure garbled circuits from one-way functions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 149\u2013178. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-53015-3_6"},{"key":"1_CR23","unstructured":"Hewitt, C.E. Paterson, M.S.: Comparative Schematology. In: Record of the Project MAC Conference on Concurrent Systems and Parallel Computation, pp. 119\u2013127. ACM, New York (1970)"},{"key":"1_CR24","unstructured":"Jafargholi, Z., Wichs, D.: Adaptive security of Yao\u2019s garbled circuits. Cryptology ePrint Archive, Report 2016\/814 (2016). http:\/\/eprint.iacr.org\/2016\/814"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Kaliski, B.: PKCS#5: password-based cryptography specification version 2.0 (2000)","DOI":"10.17487\/rfc2898"},{"issue":"4","key":"1_CR26","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1145\/322344.322354","volume":"29","author":"T Lengauer","year":"1982","unstructured":"Lengauer, T., Tarjan, R.E.: Asymptotically tight bounds on time-space trade-offs in a pebble game. J. ACM 29(4), 1087\u20131130 (1982)","journal-title":"J. ACM"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Mahmoody, M., Moran, T., Vadhan, S.P.: Publicly verifiable proofs of sequential work. In: Kleinberg, R.D. (ed.) ITCS 2013, pp. 373\u2013388. ACM, January 2013","DOI":"10.1145\/2422436.2422479"},{"key":"1_CR28","unstructured":"Narayanan, A., Bonneau, J., Felten, E.W., Miller, A., Goldfeder, S.: Bitcoin and Cryptocurrency Technology (manuscript) (2015). Accessed 8 June 2015"},{"key":"1_CR29","unstructured":"Percival, C.: Stronger key derivation via sequential memory-hard functions. In: BSDCan 2009 (2009)"},{"key":"1_CR30","unstructured":"Password hashing competition. https:\/\/password-hashing.net\/"},{"key":"1_CR31","first-page":"391","volume":"14","author":"WJ Paul","year":"1980","unstructured":"Paul, W.J., Reischuk, R.: On alternation II. A graph theoretic approach to determinism versus nondeterminism. Acta Inf. 14, 391\u2013403 (1980)","journal-title":"Acta Inf."},{"key":"1_CR32","unstructured":"Ren, L., Devadas, S.: Proof of space from stacked bipartite graphs. Cryptology ePrint Archive, Report 2016\/333 (2016). http:\/\/eprint.iacr.org\/"},{"key":"1_CR33","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0304-3975(82)90113-X","volume":"18","author":"G Schnitger","year":"1982","unstructured":"Schnitger, G.: A family of graphs with expensive depth reduction. Theor. Comput. Sci. 18, 89\u201393 (1982)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"Schnitger, G.: On depth-reduction and grates. In: 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7\u20139 November 1983, pp. 323\u2013328. IEEE Computer Society (1983)","DOI":"10.1109\/SFCS.1983.38"},{"issue":"5","key":"1_CR35","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1109\/TIT.1978.1055938","volume":"24","author":"JE Savage","year":"1978","unstructured":"Savage, J.E., Swamy, S.: Space-time trade-offs on the FFT algorithm. IEEE Trans. Inf. Theory 24(5), 563\u2013568 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/3-540-09510-1_40","volume-title":"Automata, Languages and Programming","author":"JE Savage","year":"1979","unstructured":"Savage, J.E., Swamy, S.: Space-time tradeoffs for oblivious integer multiplication. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol. 71, pp. 498\u2013504. Springer, Heidelberg (1979). doi: 10.1007\/3-540-09510-1_40"},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"Swamy, S., Savage, J.E.: Space-time tradeoffs for linear recursion. In: Aho, A.V., Zilles, S.N., Rosen, B.K. (eds) POPL, pp. 135\u2013142. ACM Press (1979)","DOI":"10.1145\/567752.567765"},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"Tompa, M.: Time-space tradeoffs for computing functions, using connectivity properties of their circuits. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 196\u2013204. ACM, New York (1978)","DOI":"10.1145\/800133.804348"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2017"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-56617-7_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T08:01:55Z","timestamp":1568966515000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-56617-7_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319566160","9783319566177"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-56617-7_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}