{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:41:38Z","timestamp":1760708498581,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642365935"},{"type":"electronic","value":"9783642365942"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"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":[[2013]]},"DOI":"10.1007\/978-3-642-36594-2_3","type":"book-chapter","created":{"date-parts":[[2013,2,7]],"date-time":"2013-02-07T02:43:27Z","timestamp":1360205007000},"page":"40-59","source":"Crossref","is-referenced-by-count":12,"title":["Hardness Preserving Reductions via Cuckoo Hashing"],"prefix":"10.1007","author":[{"given":"Itay","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iftach","family":"Haitner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moni","family":"Naor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/3-540-68339-9_27","volume-title":"Advances in Cryptology - EUROCRYPT \u201996","author":"W. Aiello","year":"1996","unstructured":"Aiello, W., Venkatesan, R.: Foiling Birthday Attacks in Length-Doubling Transformations - Benes: a non-reversible alternative to Feistel. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol.\u00a01070, pp. 307\u2013320. Springer, Heidelberg (1996)"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., Segev, G.: Backyard cuckoo hashing: Constant worst-case operations with a succinct representation. In: Proceedings of the 51th Annual Symposium on Foundations of Computer Science (FOCS), pp. 787\u2013796 (2010)","DOI":"10.1109\/FOCS.2010.80"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-642-33090-2_11","volume-title":"Algorithms \u2013 ESA 2012","author":"M. Aum\u00fcller","year":"2012","unstructured":"Aum\u00fcller, M., Dietzfelbinger, M., Woelfel, P.: Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 108\u2013120. Springer, Heidelberg (2012)"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1007\/0-387-34805-0_19","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"M. Bellare","year":"1990","unstructured":"Bellare, M., Goldwasser, S.: New Paradigms for Digital Signatures and Message Authentication Based on Non-interactive Zero Knowledge Proofs. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 194\u2013211. Springer, Heidelberg (1990)"},{"key":"3_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-48405-1_17","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"M. Bellare","year":"1999","unstructured":"Bellare, M., Goldreich, O., Krawczyk, H.: Stateless Evaluation of Pseudorandom Functions: Security beyond the Birthday Barrier. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol.\u00a01666, pp. 270\u2013287. Springer, Heidelberg (1999)"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/978-3-642-28914-9_20","volume-title":"Theory of Cryptography","author":"I. Berman","year":"2012","unstructured":"Berman, I., Haitner, I.: From Non-adaptive to Adaptive Pseudorandom Functions. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.\u00a07194, pp. 357\u2013368. Springer, Heidelberg (2012)"},{"issue":"2\/3","key":"3_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF01185212","volume":"12","author":"M. Blum","year":"1994","unstructured":"Blum, M., Evans, W.S., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. Algorithmica\u00a012(2\/3), 225\u2013244 (1994)","journal-title":"Algorithmica"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Carter, L.J., Wegman, M.N.: Universal classes of hash functions. Journal of Computer and System Sciences, 143\u2013154 (1979)","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"3_CR9","unstructured":"Chandran, N., Garg, S.: Hardness preserving constructions of pseudorandom functions, revisited. IACR Cryptology ePrint Archive 2012:616 (2012)"},{"issue":"3","key":"3_CR10","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1109\/18.841169","volume":"46","author":"B. Chor","year":"2000","unstructured":"Chor, B., Fiat, A., Naor, M., Pinkas, B.: Tracing traitors. IEEE Transactions on Information Theory\u00a046(3), 893\u2013910 (2000)","journal-title":"IEEE Transactions on Information Theory"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Woelfel, P.: Almost random graphs with simple hash functions. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 629\u2013638 (2003)","DOI":"10.1145\/780632.780634"},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/3-540-47721-7_31","volume-title":"Advances in Cryptology - CRYPTO \u201986","author":"O. Goldreich","year":"1987","unstructured":"Goldreich, O.: Towards a Theory of Software Protection. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol.\u00a0263, pp. 426\u2013439. Springer, Heidelberg (1987)"},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/3-540-39568-7_22","volume-title":"Advances in Cryptology","author":"O. Goldreich","year":"1985","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: On the Cryptographic Applications of Random Functions. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol.\u00a0196, pp. 276\u2013288. Springer, Heidelberg (1985)"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of the ACM, 792\u2013807 (1986)","DOI":"10.1145\/6490.6503"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM Journal on Computing, 1364\u20131396 (1999)","DOI":"10.1137\/S0097539793244708"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-28914-9_21","volume-title":"Theory of Cryptography","author":"A. Jain","year":"2012","unstructured":"Jain, A., Pietrzak, K., Tentes, A.: Hardness Preserving Constructions of Pseudorandom Functions. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.\u00a07194, pp. 369\u2013382. Springer, Heidelberg (2012)"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-642-34961-4_20","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2012","author":"D. Jetchev","year":"2012","unstructured":"Jetchev, D., \u00d6zen, O., Stam, M.: Understanding Adaptivity: Random Systems Revisited. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol.\u00a07658, pp. 313\u2013330. Springer, Heidelberg (2012)"},{"issue":"4","key":"3_CR18","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"L.A. Levin","year":"1987","unstructured":"Levin, L.A.: One-way functions and pseudorandom generators. Combinatorica\u00a07(4), 357\u2013363 (1987)","journal-title":"Combinatorica"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Luby, M.: Pseudorandomness and cryptographic applications. Princeton computer science notes. Princeton University Press (1996)","DOI":"10.1515\/9780691206844"},{"issue":"2","key":"3_CR20","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/0217022","volume":"17","author":"M. Luby","year":"1988","unstructured":"Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing\u00a017(2), 373\u2013386 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/3-540-46035-7_8","volume-title":"Advances in Cryptology - EUROCRYPT 2002","author":"U.M. Maurer","year":"2002","unstructured":"Maurer, U.M.: Indistinguishability of Random Systems. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol.\u00a02332, pp. 110\u2013132. Springer, Heidelberg (2002)"},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/978-3-540-24638-1_23","volume-title":"Theory of Cryptography","author":"U.M. Maurer","year":"2004","unstructured":"Maurer, U.M., Pietrzak, K.: Composition of Random Systems: When Two Weak Make One Strong. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 410\u2013427. Springer, Heidelberg (2004)"},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-540-24676-3_12","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"S. Myers","year":"2004","unstructured":"Myers, S.: Black-Box Composition Does Not Imply Adaptive Security. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol.\u00a03027, pp. 189\u2013206. Springer, Heidelberg (2004)"},{"key":"3_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-642-13858-4_12","volume-title":"Fast Software Encryption","author":"M. Nandi","year":"2010","unstructured":"Nandi, M.: A Unified Method for Improving PRF Bounds for a Class of Blockcipher Based MACs. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol.\u00a06147, pp. 212\u2013229. Springer, Heidelberg (2010)"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of psuedo-random functions. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pp. 170\u2013181 (1995)","DOI":"10.1109\/SFCS.1995.492474"},{"key":"3_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/0-387-34805-0_55","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"R. Ostrovsky","year":"1990","unstructured":"Ostrovsky, R.: An Efficient Software Protection Scheme. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 610\u2013611. Springer, Heidelberg (1990)"},{"issue":"1","key":"3_CR27","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1137\/060658400","volume":"38","author":"A. Pagh","year":"2008","unstructured":"Pagh, A., Pagh, R.: Uniform hashing in constant time and optimal space. SIAM Journal on Computing\u00a038(1), 85\u201396 (2008)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"3_CR28","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R. Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms\u00a051(2), 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"3_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/978-3-540-28628-8_7","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"J. Patarin","year":"2004","unstructured":"Patarin, J.: Security of Random Feistel Schemes with 5 or More Rounds. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol.\u00a03152, pp. 106\u2013122. Springer, Heidelberg (2004)"},{"key":"3_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-540-68164-9_14","volume-title":"Progress in Cryptology \u2013 AFRICACRYPT 2008","author":"J. Patarin","year":"2008","unstructured":"Patarin, J.: A Proof of Security in O(2 n ) for the Benes Scheme. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol.\u00a05023, pp. 209\u2013220. Springer, Heidelberg (2008)"},{"key":"3_CR31","unstructured":"Patarin, J.: Security of balanced and unbalanced feistel schemes with linear non equalities. IACR Cryptology ePrint Archive, 2010:293 (2010)"},{"key":"3_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/11535218_4","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"K. Pietrzak","year":"2005","unstructured":"Pietrzak, K.: Composition Does Not Imply Adaptive Security. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol.\u00a03621, pp. 55\u201365. Springer, Heidelberg (2005)"},{"key":"3_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/11761679_20","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"K. Pietrzak","year":"2006","unstructured":"Pietrzak, K.: Composition Implies Adaptive Security in Minicrypt. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.\u00a04004, pp. 328\u2013338. Springer, Heidelberg (2006)"},{"issue":"3","key":"3_CR34","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0097539701386216","volume":"33","author":"A. Siegel","year":"2004","unstructured":"Siegel, A.: On universal classes of extremely random constant-time hash functions. SIAM Journal on Computing\u00a033(3), 505\u2013543 (2004)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"3_CR35","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","volume":"22","author":"M.N. Wegman","year":"1981","unstructured":"Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci.\u00a022(3), 265\u2013279 (1981)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36594-2_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T20:11:20Z","timestamp":1745957480000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36594-2_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642365935","9783642365942"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36594-2_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}