{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,27]],"date-time":"2025-04-27T05:00:21Z","timestamp":1745730021701},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662583869"},{"type":"electronic","value":"9783662583876"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-662-58387-6_18","type":"book-chapter","created":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T11:03:39Z","timestamp":1567076619000},"page":"329-346","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling"],"prefix":"10.1007","author":[{"given":"Jeremiah","family":"Blocki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samson","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,12,7]]},"reference":[{"key":"18_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). \n                      https:\/\/doi.org\/10.1007\/978-3-662-53008-5_9"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Alwen, J., Blocki, J.: Towards practical attacks on Argon2i and balloon hashing. In: 2017 IEEE European Symposium on Security and Privacy, EuroS&P, pp. 142\u2013157 (2017)","DOI":"10.1109\/EuroSP.2017.47"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Alwen, J., Blocki, J., Harsha, B.: Practical graphs for optimal side-channel resistant memory-hard functions. In: ACM CCS 17, pp. 1001\u20131017. ACM Press (2017)","DOI":"10.1145\/3133956.3134031"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-56617-7_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"J Alwen","year":"2017","unstructured":"Alwen, J., Blocki, J., Pietrzak, K.: Depth-robust graphs and their cumulative memory complexity. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 3\u201332. Springer, Cham (2017). \n                      https:\/\/doi.org\/10.1007\/978-3-319-56617-7_1"},{"key":"18_CR5","unstructured":"Abadi, M., Burrows, M., Wobber, T.: Moderately hard, memory-bound functions. In: Proceedings of the Network and Distributed System Security Symposium, NDSS 2003, San Diego, California, USA (2003)"},{"key":"18_CR6","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). \n                      http:\/\/eprint.iacr.org\/2014\/238"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/978-3-319-70500-2_17","volume-title":"Theory of Cryptography","author":"J Alwen","year":"2017","unstructured":"Alwen, J., Tackmann, B.: Moderately hard functions: definition, instantiations, and applications. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 493\u2013526. Springer, Cham (2017). \n                      https:\/\/doi.org\/10.1007\/978-3-319-70500-2_17"},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/978-3-662-53887-6_8","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2016","author":"D Boneh","year":"2016","unstructured":"Boneh, D., Corrigan-Gibbs, H., Schechter, S.: Balloon hashing: a memory-hard function providing provable protection against sequential attacks. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 220\u2013248. Springer, Heidelberg (2016). \n                      https:\/\/doi.org\/10.1007\/978-3-662-53887-6_8"},{"key":"18_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). \n                      http:\/\/eprint.iacr.org\/2015\/430"},{"key":"18_CR10","unstructured":"Biryukov, A., Dinu, D., Khovratovich, D.: Argon2 password hash. Version 1.3 (2016). \n                      https:\/\/www.cryptolux.org\/images\/0\/0d\/Argon2.pdf"},{"key":"18_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":"18_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/978-3-662-48800-3_26","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2015","author":"A Biryukov","year":"2015","unstructured":"Biryukov, A., Khovratovich, D.: Tradeoff cryptanalysis of memory-hard functions. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 633\u2013657. Springer, Heidelberg (2015). \n                      https:\/\/doi.org\/10.1007\/978-3-662-48800-3_26"},{"issue":"12","key":"18_CR13","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"B Bresar","year":"2011","unstructured":"Bresar, B., Kardos, F., Katrenic, J., Semanisin, G.: Minimum k-path vertex cover. Discrete Appl. Math. 159(12), 1189\u20131195 (2011)","journal-title":"Discrete Appl. Math."},{"key":"18_CR14","unstructured":"Blocki, J., Zhou, S.: On the computational complexity of minimal cumulative cost graph pebbling. CoRR, abs\/1609.04449 (2016)"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/978-3-319-70500-2_15","volume-title":"Theory of Cryptography","author":"J Blocki","year":"2017","unstructured":"Blocki, J., Zhou, S.: On the depth-robustness and cumulative pebbling cost of Argon2i. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 445\u2013465. Springer, Cham (2017). \n                      https:\/\/doi.org\/10.1007\/978-3-319-70500-2_15"},{"key":"18_CR16","unstructured":"Corrigan-Gibbs, H., Boneh, D., Schechter, S.: Balloon hashing: provably space-hard hash functions with data-independent access patterns. Cryptology ePrint Archive, Report 2016\/027, Version: 20160601:225540 (2016). \n                      http:\/\/eprint.iacr.org\/"},{"key":"18_CR17","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":"18_CR18","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":"18_CR19","unstructured":"Demaine, E.: 6.890 algorithmic lower bounds: fun with hardness proofs, September 2014. \n                      http:\/\/ocw.mit.edu"},{"key":"18_CR20","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). \n                      https:\/\/doi.org\/10.1007\/978-3-662-48000-7_29"},{"key":"18_CR21","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). \n                      https:\/\/doi.org\/10.1007\/978-3-540-45146-4_25"},{"key":"18_CR22","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). \n                      https:\/\/doi.org\/10.1007\/11535218_3"},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439\u2013485 (2005)","journal-title":"Ann. Math."},{"key":"18_CR24","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0898-1221(75)90037-1","volume":"1","author":"P Erd\u00f6s","year":"1975","unstructured":"Erd\u00f6s, P., Graham, R.L., Szemeredi, E.: On sparse graphs with dense long paths. Comput. Math. Appl. 1, 365\u2013369 (1975)","journal-title":"Comput. Math. Appl."},{"key":"18_CR25","unstructured":"Forler, C., Lucks, S., Wenzel, J.: Catena: a memory-consuming password scrambler. IACR Cryptology ePrint Archive 2013:525 (2013)"},{"issue":"4","key":"18_CR26","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"MR Garey","year":"1975","unstructured":"Garey, M.R., Johnson, D.S.: Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput. 4(4), 397\u2013411 (1975)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"18_CR27","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0209038","volume":"9","author":"JR Gilbert","year":"1980","unstructured":"Gilbert, J.R., Lengauer, T., Tarjan, R.E.: The pebbling problem is complete in polynomial space. SIAM J. Comput. 9(3), 513\u2013524 (1980)","journal-title":"SIAM J. Comput."},{"key":"18_CR28","unstructured":"Hewitt, C.E., Paterson, M.S.: Record of the project MAC conference on concurrent systems and parallel computation (1970)"},{"issue":"6","key":"18_CR29","doi-asserted-by":"publisher","first-page":"2622","DOI":"10.1137\/080713513","volume":"39","author":"P Hertel","year":"2010","unstructured":"Hertel, P., Pitassi, T.: The pspace-completeness of black-white pebbling. SIAM J. Comput. 39(6), 2622\u20132682 (2010)","journal-title":"SIAM J. Comput."},{"key":"18_CR30","doi-asserted-by":"crossref","unstructured":"Kaliski, B.: Pkcs# 5: password-based cryptography specification version 2.0 (2000)","DOI":"10.17487\/rfc2898"},{"key":"18_CR31","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the Thirty-Fourth annual ACM Symposium on Theory of Computing, pp. 767\u2013775. ACM (2002)","DOI":"10.1145\/510014.510017"},{"issue":"3","key":"18_CR32","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2- \n                      \n                        \n                      \n                      \n$$\\epsilon $$\n\n                    . J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR33","doi-asserted-by":"crossref","unstructured":"Lee, E.: Partitioning a graph into small pieces with applications to path transversal. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1546\u20131558 (2017)","DOI":"10.1137\/1.9781611974782.101"},{"key":"18_CR34","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":"18_CR35","unstructured":"Narayanan, A., Bonneau, J., Felten, E.W., Miller, A., Goldfeder, S.: Bitcoin and cryptocurrency technology (manuscript) (2015). Accessed 8 June 2015"},{"key":"18_CR36","unstructured":"Percival, C.: Stronger key derivation via sequential memory-hard functions. In: BSDCan 2009 (2009)"},{"key":"18_CR37","unstructured":"Password hashing competition. \n                      https:\/\/password-hashing.net\/"},{"key":"18_CR38","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":"18_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/978-3-662-53641-4_11","volume-title":"Theory of Cryptography","author":"L Ren","year":"2016","unstructured":"Ren, L., Devadas, S.: Proof of space from stacked expanders. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 262\u2013285. Springer, Heidelberg (2016). \n                      https:\/\/doi.org\/10.1007\/978-3-662-53641-4_11"},{"key":"18_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1007\/978-3-319-70500-2_16","volume-title":"Theory of Cryptography","author":"L Ren","year":"2017","unstructured":"Ren, L., Devadas, S.: Bandwidth hard functions for ASIC resistance. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 466\u2013492. Springer, Cham (2017). \n                      https:\/\/doi.org\/10.1007\/978-3-319-70500-2_16"},{"key":"18_CR41","doi-asserted-by":"publisher","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":"18_CR42","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":"18_CR43","doi-asserted-by":"publisher","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":"18_CR44","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). \n                      https:\/\/doi.org\/10.1007\/3-540-09510-1_40"},{"key":"18_CR45","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":"18_CR46","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","Financial Cryptography and Data Security"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-58387-6_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T11:06:36Z","timestamp":1567076796000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-58387-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783662583869","9783662583876"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-58387-6_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"7 December 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Financial Cryptography and Data Security","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nieuwpoort","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cura\u00e7ao","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 February 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 March 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fc2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/fc18.ifca.ai\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"HotCRP","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"110","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"27","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3,27","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3,27","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}