{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:16:34Z","timestamp":1773479794577,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662536407","type":"print"},{"value":"9783662536414","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","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":[[2016]]},"DOI":"10.1007\/978-3-662-53641-4_11","type":"book-chapter","created":{"date-parts":[[2016,10,21]],"date-time":"2016-10-21T15:48:14Z","timestamp":1477064894000},"page":"262-285","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":40,"title":["Proof of Space from Stacked Expanders"],"prefix":"10.1007","author":[{"given":"Ling","family":"Ren","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivas","family":"Devadas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,22]]},"reference":[{"key":"11_CR1","unstructured":"Zoom Hash Scrypt ASIC. \n                      http:\/\/zoomhash.com\/collections\/asics\n                      \n                    . Accessed: 20 May 2016"},{"issue":"2","key":"11_CR2","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1145\/1064340.1064341","volume":"5","author":"M Abadi","year":"2005","unstructured":"Abadi, M., Burrows, M., Manasse, M., Wobber, T.: Moderately hard, memory-bound functions. ACM Trans. Internet Technol. 5(2), 299\u2013327 (2005)","journal-title":"ACM Trans. Internet Technol."},{"issue":"2","key":"11_CR3","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s13389-013-0063-5","volume":"4","author":"LC Almeida","year":"2014","unstructured":"Almeida, L.C., Andrade, E.R., Barreto, P.S.L.M., Marcos, A., Simplicio Jr., M.A.: Lyra: password-based key derivation with tunable memory and processing costs. J. Crypt. Eng. 4(2), 75\u201389 (2014)","journal-title":"J. Crypt. Eng."},{"key":"11_CR4","unstructured":"Alon, N., Capalbo, M.: Smaller explicit superconcentrators. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 340\u2013346. Society for Industrial and Applied Mathematics (2003)"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Alwen, J., Blocki, J.: Efficiently computing data-independent memory-hard functions. Cryptology ePrint Archive, Report 2016\/115 (2016)","DOI":"10.1007\/978-3-662-53008-5_9"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Alwen, J., Blocki, J.: Towards practical attacks on argon2i and balloon hashing. Cryptology ePrint Archive, Report 2016\/759 (2016)","DOI":"10.1109\/EuroSP.2017.47"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/978-3-662-49896-5_13","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"J Alwen","year":"2016","unstructured":"Alwen, J., Chen, B., Kamath, C., Kolmogorov, V., Pietrzak, K., Tessaro, S.: On the complexity of scrypt and proofs of space in the parallel random oracle model. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 358\u2013387. Springer, Heidelberg (2016). doi:\n                      10.1007\/978-3-662-49896-5_13"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 595\u2013603. ACM (2015)","DOI":"10.1145\/2746539.2746622"},{"key":"11_CR9","unstructured":"Andersen, D.G.: Exploiting time-memory tradeoffs in cuckoo cycle (2014). \n                      https:\/\/www.cs.cmu.edu\/~dga\/crypto\/cuckoo\/analysis.pdf\n                      \n                    . Accessed Aug 2016"},{"key":"11_CR10","unstructured":"Asanovic, K., Bodik, R., Catanzaro, B.C., Gebis, J.J., Husbands, P., Keutzer, K., Patterson, D.A., Plishker, W.L., Shalf, J., Williams, S.W.: The landscape of parallel computing research: a view from berkeley. Technical Report UCB\/EECS-2006-183, EECS Department, University of California, Berkeley (2006)"},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1007\/978-3-319-10879-7_31","volume-title":"Security and Cryptography for Networks","author":"G Ateniese","year":"2014","unstructured":"Ateniese, G., Bonacina, I., Faonio, A., Galesi, N.: Proofs of space: when space is of the essence. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 538\u2013557. Springer, Heidelberg (2014)"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Ateniese, G., Burns, R., Curtmola, R., Herring, J., Kissner, L., Peterson, Z., Song, D.: Provable data possession at untrusted stores. In: Proceedings of the 14th ACM Conference on Computer and Communications Security, pp. 598\u2013609. ACM (2007)","DOI":"10.1145\/1315245.1315318"},{"key":"11_CR13","unstructured":"Back, A.: Hashcash-a denial of service counter-measure (2002)"},{"issue":"3","key":"11_CR14","first-page":"81","volume":"17","author":"Leonid Alexandrovich Bassalygo","year":"1981","unstructured":"Leonid Alexandrovich Bassalygo: Asymptotically optimal switching circuits. Problemy Peredachi Informatsii 17(3), 81\u201388 (1981)","journal-title":"Problemy Peredachi Informatsii"},{"key":"11_CR15","unstructured":"Biryukov, A., Dinu, D., Khovratovich, D.: Fast and tradeoff-resilient memory-hard functions for cryptocurrencies and password hashing (2015)"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Biryukov, A., Khovratovich, D.: Tradeoff cryptanalysis of memory-hard functions. Cryptology ePrint Archive, Report 2015\/227 (2015)","DOI":"10.1007\/978-3-662-48800-3_26"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Biryukov, A., Khovratovich, D.: Equihash: asymmetric proof-of-work based on the generalized birthday problem. In: NDSS (2016)","DOI":"10.14722\/ndss.2016.23108"},{"issue":"8","key":"11_CR18","doi-asserted-by":"publisher","first-page":"1765","DOI":"10.1002\/j.1538-7305.1979.tb02972.x","volume":"58","author":"FRK Chung","year":"1979","unstructured":"Chung, F.R.K.: On concentrators, superconcentrators, generalizers, and nonblocking networks. Bell Syst. Techn. J. 58(8), 1765\u20131777 (1979)","journal-title":"Bell Syst. Techn. J."},{"key":"11_CR19","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, pp. 29\u201333. ACM (1973)","DOI":"10.1145\/800125.804032"},{"key":"11_CR20","unstructured":"Corrigan-Gibbs, H., Boneh, D., Schechter, S.: Balloon hashing: a provably memory-hard function with a data-independent access pattern. Cryptology ePrint Archive, Report 2016\/027 (2016)"},{"key":"11_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). doi:\n                      10.1007\/978-3-540-45146-4_25"},{"key":"11_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/3-540-48071-4_10","volume-title":"Advances in Cryptology - CRYPTO \u201992","author":"C Dwork","year":"1993","unstructured":"Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139\u2013147. Springer, Heidelberg (1993)"},{"key":"11_CR23","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.M.: Pebbling and proofs of work. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 37\u201354. Springer, Heidelberg (2005)"},{"key":"11_CR24","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)"},{"key":"11_CR25","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)"},{"key":"11_CR26","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)"},{"key":"11_CR27","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-319-24192-0_1","volume-title":"Technology and Practice of Passwords","author":"Christian Forler","year":"2015","unstructured":"Forler, C., List, E., Lucks, S., Wenzel, J.: Overview of the candidates for the password hashing competition (2015)"},{"key":"11_CR28","unstructured":"Forler, C., Lucks, S., Wenzel, J.: Catena: a memory-consuming password-scrambling framework. Cryptology ePrint Archive, Report 2013\/525 (2013)"},{"key":"11_CR29","doi-asserted-by":"crossref","unstructured":"Hopcroft, J., Paul, W., Valiant, L.: On time versus space and related problems. In: 16th Annual Symposium on Foundations of Computer Science, pp. 57\u201364. IEEE (1975)","DOI":"10.1109\/SFCS.1975.23"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Juels, A., Kaliski Jr., B.S.: PORs: proofs of retrievability for large files. In: Proceedings of the 14th ACM Conference on Computer and Communications Security, pp. 584\u2013597. ACM (2007)","DOI":"10.1145\/1315245.1315317"},{"key":"11_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1007\/978-3-319-10879-7_30","volume-title":"Security and Cryptography for Networks","author":"NP Karvelas","year":"2014","unstructured":"Karvelas, N.P., Kiayias, A.: Efficient proofs of secure erasure. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 520\u2013537. Springer, Heidelberg (2014)"},{"issue":"4","key":"11_CR32","doi-asserted-by":"publisher","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":"11_CR33","unstructured":"Lerner, S.D.: Strict memory hard hashing functions (preliminary v0. 3, 01-19-14)"},{"key":"11_CR34","doi-asserted-by":"crossref","unstructured":"Mahmoody, M., Moran, T., Vadhan, S.: Publicly verifiable proofs of sequential work. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pp. 373\u2013388. ACM (2013)","DOI":"10.1145\/2422436.2422479"},{"key":"11_CR35","unstructured":"Moran, T., Orlov, I.: Proofs of space-time and rational proofs of storage. Cryptology ePrint Archive, Report 2016\/035 (2016)"},{"key":"11_CR36","unstructured":"Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)"},{"issue":"2","key":"11_CR37","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF00289150","volume":"10","author":"WJ Paul","year":"1978","unstructured":"Paul, W.J., Tarjan, R.E.: Time-space trade-offs in a pebble game. Acta Informatica 10(2), 111\u2013115 (1978)","journal-title":"Acta Informatica"},{"issue":"1","key":"11_CR38","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BF01683275","volume":"10","author":"WJ Paul","year":"1976","unstructured":"Paul, W.J., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. Math. Syst. Theory 10(1), 239\u2013251 (1976)","journal-title":"Math. Syst. Theory"},{"key":"11_CR39","unstructured":"Percival, C.: Stronger key derivation via sequential memory-hard functions (2009)"},{"key":"11_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-642-15497-3_39","volume-title":"Computer Security \u2013 ESORICS 2010","author":"D Perito","year":"2010","unstructured":"Perito, D., Tsudik, G.: Secure code update for embedded devices via proofs of secure erasure. In: Gritzalis, D., Preneel, B., Theoharidou, M. (eds.) ESORICS 2010. LNCS, vol. 6345, pp. 643\u2013662. Springer, Heidelberg (2010)"},{"key":"11_CR41","unstructured":"Peslyak, A.: yescrypt - a password hashing competition submission (2014). \n                      https:\/\/password-hashing.net\/submissions\/specs\/yescrypt-v2.pdf\n                      \n                    . Accessed Aug 2016"},{"key":"11_CR42","unstructured":"Pinsker, M.S.: On the complexity of a concentrator. In: 7th International Telegraffic Conference, vol. 4 (1973)"},{"issue":"1","key":"11_CR43","doi-asserted-by":"publisher","first-page":"26","DOI":"10.2307\/2308012","volume":"62","author":"H Robbins","year":"1955","unstructured":"Robbins, H.: A remark on Stirling\u2019s formula. Am. Math. Monthly 62(1), 26\u201329 (1955)","journal-title":"Am. Math. Monthly"},{"key":"11_CR44","unstructured":"Sch\u00f6ning, U.: Better expanders and superconcentrators by Kolmogorov complexity. In: SIROCCO, pp. 138\u2013150 (1997)"},{"issue":"4","key":"11_CR45","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.ipl.2006.01.006","volume":"98","author":"U Sch\u00f6ning","year":"2006","unstructured":"Sch\u00f6ning, U.: Smaller superconcentrators of density 28. Inf. Process. Lett. 98(4), 127\u2013129 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"11_CR46","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1137\/0204020","volume":"4","author":"R Sethi","year":"1975","unstructured":"Sethi, R.: Complete register allocation problems. SIAM J. Comput. 4(3), 226\u2013248 (1975)","journal-title":"SIAM J. Comput."},{"key":"11_CR47","unstructured":"Smith, A., Zhang, Y.: Near-linear time, leakage-resilient key evolution schemes from expander graphs. Cryptology ePrint Archive, Report 2013\/864 (2013)"},{"key":"11_CR48","unstructured":"Tromp, J.: Cuckoo cycle: a memory-hard proof-of-work system (2014)"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53641-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T00:04:18Z","timestamp":1603411458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53641-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662536407","9783662536414"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53641-4_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 October 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 November 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 November 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}