{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:23:26Z","timestamp":1764174206941,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662479995"},{"type":"electronic","value":"9783662480007"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-48000-7_9","type":"book-chapter","created":{"date-parts":[[2015,7,31]],"date-time":"2015-07-31T02:27:46Z","timestamp":1438309666000},"page":"173-190","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Parallel Hashing via List Recoverability"],"prefix":"10.1007","author":[{"given":"Iftach","family":"Haitner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eran","family":"Omri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronen","family":"Shaltiel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,1]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Barak, B.: How to go beyond the black-box simulation barrier. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 106\u2013115 (2001)","key":"9_CR1","DOI":"10.1109\/SFCS.2001.959885"},{"issue":"2","key":"9_CR2","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/050646445","volume":"38","author":"E Ben-Sasson","year":"2008","unstructured":"Ben-Sasson, E., Sudan, M.: Short pcps with polylog query complexity. SIAM J. Comput. 38(2), 551\u2013607 (2008)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10207-013-0220-y","volume":"13","author":"G Bertoni","year":"2014","unstructured":"Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: Sufficient conditions for sound tree and sequential hashing modes. Int. J. Inf. Sec. 13(4), 335\u2013353 (2014a)","journal-title":"Int. J. Inf. Sec."},{"issue":"1","key":"9_CR4","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1080\/01611194.2013.856818","volume":"38","author":"G Bertoni","year":"2014","unstructured":"Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: The making of KECCAK. Cryptologia 38(1), 26\u201360 (2014b). doi: 10.1080\/01611194.2013.856818 . http:\/\/dx.doi.org\/10.1080\/01611194.2013.856818","journal-title":"Cryptologia"},{"doi-asserted-by":"crossref","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: Proceedings of the 23th Annual Symposium on Foundations of Computer Science (FOCS), pp. 112\u2013117 (1982)","key":"9_CR5","DOI":"10.1109\/SFCS.1982.72"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-540-74143-5_15","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"R Canetti","year":"2007","unstructured":"Canetti, R., Rivest, R., Sudan, M., Trevisan, L., Vadhan, S.P., Wee, H.M.: Amplifying collision resistance: a complexity-theoretic treatment. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 264\u2013283. Springer, Heidelberg (2007)"},{"key":"9_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/11535218_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"J-S Coron","year":"2005","unstructured":"Coron, J.-S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damg\u00e5rd revisited: how to construct a hash function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430\u2013448. Springer, Heidelberg (2005)"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/3-540-39118-5_19","volume-title":"Advances in Cryptology - EUROCRYPT \u201987","author":"IB Damg\u00e5rd","year":"1988","unstructured":"Damg\u00e5rd, I.B.: Collision free hash functions and public key signature schemes. In: Price, W.L., Chaum, D. (eds.) EUROCRYPT 1987. LNCS, vol. 304, pp. 203\u2013216. Springer, Heidelberg (1988)"},{"issue":"3","key":"9_CR9","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s001459900026","volume":"10","author":"I Damg\u00e5rd","year":"1997","unstructured":"Damg\u00e5rd, I., Pedersen, T.P., Pfitzmann, B.: On the existence of statistically hiding bit commitment schemes and fail-stop signatures. J. Cryptol. 10(3), 163\u2013194 (1997)","journal-title":"J. Cryptol."},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/0-387-34805-0_39","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"IB Damg\u00e5rd","year":"1990","unstructured":"Damg\u00e5rd, I.B.: A design principle for hash functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416\u2013427. Springer, Heidelberg (1990)"},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-642-20465-4_19","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"Y Dodis","year":"2011","unstructured":"Dodis, Y., Steinberger, J.: Domain extension for MACs beyond the birthday barrier. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 323\u2013342. Springer, Heidelberg (2011)"},{"key":"9_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","volume-title":"Advances in Cryptology - CRYPTO \u201986","author":"A Fiat","year":"1987","unstructured":"Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186\u2013194. Springer, Heidelberg (1987)"},{"key":"9_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/BFb0052231","volume-title":"Advances in Cryptology - CRYPTO \u201997","author":"O Goldreich","year":"1997","unstructured":"Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112\u2013131. Springer, Heidelberg (1997)"},{"doi-asserted-by":"crossref","unstructured":"Guruswami, V.: List Decoding of Error-Correcting Codes. Ph.D. thesis, Massachusetts Institute of Technology (2005)","key":"9_CR14","DOI":"10.1007\/b104335"},{"doi-asserted-by":"crossref","unstructured":"Guruswami, V., Indyk, P.: Expander-based constructions of efficiently decodable codes. In: 42nd Annual Symposium on Foundations of Computer Science, pp. 658\u2013667 (2001)","key":"9_CR15","DOI":"10.1109\/SFCS.2001.959942"},{"issue":"1","key":"9_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TIT.2007.911222","volume":"54","author":"V Guruswami","year":"2008","unstructured":"Guruswami, V., Rudra, A.: Explicit codes achieving list decoding capacity: error-correction with optimal redundancy. IEEE Trans. Inf. Theory 54(1), 135\u2013150 (2008)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"6","key":"9_CR17","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.782097","volume":"45","author":"V Guruswami","year":"1999","unstructured":"Guruswami, V., Sudan, M.: Improved decoding of reed-solomon and algebraic-geometry codes. IEEE Trans. Inf. Theory 45(6), 1757\u20131767 (1999)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"9_CR18","doi-asserted-by":"publisher","first-page":"20:1","DOI":"10.1145\/1538902.1538904","volume":"56","author":"V Guruswami","year":"2009","unstructured":"Guruswami, V., Umans, C., Vadhan, S.P.: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM 56(4), 20:1\u201320:34 (2009)","journal-title":"J. ACM"},{"issue":"1","key":"9_CR19","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/130938438","volume":"44","author":"I Haitner","year":"2015","unstructured":"Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols - tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput. 44(1), 193\u2013242 (2015a). Preliminary version in STOC\u201907","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Haitner, I., Ishai, Y., Omri, E., Shaltiel, R.: Parallel hashing via list recoverability (2015b). www.cs.tau.ac.il\/~iftachh\/papers\/CRHDomainExtension\/CRH.pdf . Full version of this paper","key":"9_CR20","DOI":"10.1007\/978-3-662-48000-7_9"},{"key":"9_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/3-540-68697-5_16","volume-title":"Advances in Cryptology - CRYPTO \u201996","author":"S Halevi","year":"1996","unstructured":"Halevi, S., Micali, S.: Practical and provably-secure commitment schemes from collision-free hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 201\u2013215. Springer, Heidelberg (1996)"},{"doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract).In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), pp. 723\u2013732 (1992)","key":"9_CR22","DOI":"10.1145\/129712.129782"},{"unstructured":"Kilian, J.: On the complexity of bounded-interaction and noninteractive zero-knowledge proofs. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 466\u2013477 (1994)","key":"9_CR23"},{"unstructured":"Lucks, S.: Design principles for iterated hash functions. Technical report, Cryptology ePrint Archive (2004)","key":"9_CR24"},{"key":"9_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/11787006_13","volume-title":"Automata, Languages and Programming","author":"V Lyubashevsky","year":"2006","unstructured":"Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 144\u2013155. Springer, Heidelberg (2006)"},{"key":"9_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-540-74143-5_11","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"UM Maurer","year":"2007","unstructured":"Maurer, U.M., Tessaro, S.: Domain extension of public random functions: beyond the birthday barrier. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 187\u2013204. Springer, Heidelberg (2007)"},{"key":"9_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-540-24638-1_2","volume-title":"Theory of Cryptography","author":"UM Maurer","year":"2004","unstructured":"Maurer, U.M., Renner, R.S., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21\u201339. Springer, Heidelberg (2004)"},{"key":"9_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/3-540-48184-2_32","volume-title":"Advances in Cryptology - CRYPTO \u201987","author":"RC Merkle","year":"1988","unstructured":"Merkle, R.C.: A digital signature based on a conventional encryption function. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 369\u2013378. Springer, Heidelberg (1988)"},{"key":"9_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/0-387-34805-0_21","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"RC Merkle","year":"1990","unstructured":"Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218\u2013238. Springer, Heidelberg (1990)"},{"issue":"4","key":"9_CR30","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S Micali","year":"2000","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253\u20131298 (2000). Preliminary version in FOCS 1994","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 33\u201343. ACM Press (1989)","key":"9_CR31","DOI":"10.1145\/73007.73011"},{"doi-asserted-by":"crossref","unstructured":"Parvaresh, F., Vardy, A.: Correcting errors beyond the Guruswami-Sudan radius in polynomial time. In: 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, pp. 285\u2013294 (2005)","key":"9_CR32","DOI":"10.1109\/SFCS.2005.29"},{"key":"9_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/11681878_8","volume-title":"Theory of Cryptography","author":"C Peikert","year":"2006","unstructured":"Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 145\u2013166. Springer, Heidelberg (2006)"},{"key":"9_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/978-3-540-85174-5_24","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"P Rogaway","year":"2008","unstructured":"Rogaway, P., Steinberger, J.P.: Constructing cryptographic hash functions from fixed-key blockciphers. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 433\u2013450. Springer, Heidelberg (2008)"},{"key":"9_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-540-70583-3_52","volume-title":"Automata, Languages and Programming","author":"T Shrimpton","year":"2008","unstructured":"Shrimpton, T., Stam, M.: Building a collision-resistant compression function from non-compressing primitives. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 643\u2013654. Springer, Heidelberg (2008)"},{"key":"9_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/BFb0054137","volume-title":"Advances in Cryptology - EUROCRYPT \u201998","author":"DR Simon","year":"1998","unstructured":"Simon, D.R.: Findings collisions on a one-way street: can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334\u2013345. Springer, Heidelberg (1998)"},{"key":"9_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/978-3-540-85174-5_22","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"M Stam","year":"2008","unstructured":"Stam, M.: Beyond uniformity: better security\/efficiency tradeoffs for compression functions. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 397\u2013412. Springer, Heidelberg (2008)"},{"key":"9_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/978-3-642-32009-5_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"J Steinberger","year":"2012","unstructured":"Steinberger, J., Sun, X., Yang, Z.: Stam\u2019s conjecture and threshold phenomena in collision resistance. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 384\u2013405. Springer, Heidelberg (2012)"},{"issue":"1","key":"9_CR39","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jcom.1997.0439","volume":"13","author":"M Sudan","year":"1997","unstructured":"Sudan, M.: Decoding of reed solomon codes beyond the error-correction bound. J. Complex. 13(1), 180\u2013193 (1997)","journal-title":"J. Complex."},{"key":"9_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/11426639_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"X Wang","year":"2005","unstructured":"Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19\u201335. Springer, Heidelberg (2005)"},{"doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Theory and applications of trapdoor functions. In: Proceedings of the 23th Annual Symposium on Foundations of Computer Science (FOCS), pp. 80\u201391 (1982)","key":"9_CR41","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology -- CRYPTO 2015"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48000-7_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T20:40:21Z","timestamp":1748551221000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48000-7_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662479995","9783662480007"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48000-7_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"1 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}