{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:58Z","timestamp":1766281018042,"version":"3.41.0"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,5,7]],"date-time":"2018-05-07T00:00:00Z","timestamp":1525651200000},"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":["J Cryptol"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00145-018-9293-0","type":"journal-article","created":{"date-parts":[[2018,5,7]],"date-time":"2018-05-07T19:21:49Z","timestamp":1525720909000},"page":"361-392","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Hardness-Preserving Reductions via Cuckoo Hashing"],"prefix":"10.1007","volume":"32","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","published-online":{"date-parts":[[2018,5,7]]},"reference":[{"key":"9293_CR1","doi-asserted-by":"crossref","unstructured":"W.\u00a0Aiello, R.\u00a0Venkatesan, Foiling birthday attacks in length-doubling transformations - benes: A non-reversible alternative to feistel, in Advances in Cryptology\u2014EUROCRYPT \u201996, pp. 307\u2013320 (1996)","DOI":"10.1007\/3-540-68339-9_27"},{"key":"9293_CR2","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Arbitman, M.\u00a0Naor, G.\u00a0Segev, 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":"9293_CR3","doi-asserted-by":"crossref","unstructured":"M.\u00a0Aum\u00fcller, M.\u00a0Dietzfelbinger, P.\u00a0Woelfel, Explicit and efficient hash families suffice for cuckoo hashing with a stash, in L.\u00a0Epstein and P.\u00a0Ferragina, editors, ESA, volume 7501 of Lecture Notes in Computer Science (Springer, 2012), pp. 108\u2013120","DOI":"10.1007\/978-3-642-33090-2_11"},{"issue":"3","key":"9293_CR4","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-013-9840-x","volume":"70","author":"M Aum\u00fcller","year":"2014","unstructured":"M.\u00a0Aum\u00fcller, M.\u00a0Dietzfelbinger, P.\u00a0Woelfel, Explicit and efficient hash families suffice for cuckoo hashing with a stash. Algorithmica, 70(3), 428\u2013456, (2014)","journal-title":"Algorithmica"},{"key":"9293_CR5","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, S.\u00a0Goldwasser, New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs, in Advances in Cryptology\u2014CRYPTO \u201989, pp. 194\u2013211 (1989)","DOI":"10.1007\/0-387-34805-0_19"},{"key":"9293_CR6","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, R.\u00a0Canetti, H.\u00a0Krawczyk, Pseudorandom functions revisited: The cascade construction and its concrete security, in FOCS, pp. 514\u2013523 (1996)","DOI":"10.1109\/SFCS.1996.548510"},{"key":"9293_CR7","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, O.\u00a0Goldreich, H.\u00a0Krawczyk, Stateless evaluation of pseudorandom functions: Security beyond the birthday barrier, in Advances in Cryptology\u2014CRYPTO \u201999, pp. 270\u2013287 (1999)","DOI":"10.1007\/3-540-48405-1_17"},{"issue":"2","key":"9293_CR8","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00145-013-9169-2","volume":"28","author":"I Berman","year":"2015","unstructured":"I.\u00a0Berman, I.\u00a0Haitner, From non-adaptive to adaptive pseudorandom functions. J. Cryptology, 28(2), 297\u2013311 (2015)","journal-title":"J. Cryptol."},{"key":"9293_CR9","doi-asserted-by":"crossref","unstructured":"I.\u00a0Berman, I.\u00a0Haitner, I.\u00a0Komargodski, M.\u00a0Naor, Hardness preserving reductions via cuckoo hashing, in Theory of Cryptography\u201410th Theory of Cryptography Conference, TCC 2013, pp. 40\u201359 (2013)","DOI":"10.1007\/978-3-642-36594-2_3"},{"key":"9293_CR10","doi-asserted-by":"crossref","unstructured":"O.\u00a0Billet, J.\u00a0Etrog, H.\u00a0Gilbert, Lightweight privacy preserving authentication for rfid using a stream cipher, in 18th International Symposium on the Foundations of Software Engineering (FSE), pp. 55\u201374 (2010)","DOI":"10.1007\/978-3-642-13858-4_4"},{"issue":"2\/3","key":"9293_CR11","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF01185212","volume":"12","author":"M Blum","year":"1994","unstructured":"M.\u00a0Blum, W.S. Evans, P.\u00a0Gemmell, S.\u00a0Kannan, M.\u00a0Naor, Checking the correctness of memories. Algorithmica, 12(2\/3), 225\u2013244 (1994)","journal-title":"Algorithmica"},{"key":"9293_CR12","doi-asserted-by":"crossref","unstructured":"L.J. Carter, M.N. Wegman, Universal classes of hash functions. J. Comput. Syst. Sci., 143\u2013154 (1979)","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"9293_CR13","doi-asserted-by":"crossref","unstructured":"N.\u00a0Chandran, S.\u00a0Garg, Balancing output length and query bound in hardness preserving constructions of pseudorandom functions, in Progress in Cryptology\u2014INDOCRYPT 2014, pp. 89\u2013103 (2014)","DOI":"10.1007\/978-3-319-13039-2_6"},{"issue":"3","key":"9293_CR14","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1109\/18.841169","volume":"46","author":"B Chor","year":"2000","unstructured":"B.\u00a0Chor, A.\u00a0Fiat, M.\u00a0Naor, B.\u00a0Pinkas, Tracing traitors. IEEE Transactions on Information Theory, 46(3), 893\u2013910 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1\u20132","key":"9293_CR15","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2007.02.054","volume":"380","author":"M Dietzfelbinger","year":"2007","unstructured":"M.\u00a0Dietzfelbinger, C.\u00a0Weidling, Balanced allocation and dictionaries with tightly packed constant size bins. Theor. Comput. Sci., 380(1-2), 47\u201368, (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9293_CR16","doi-asserted-by":"crossref","unstructured":"M.\u00a0Dietzfelbinger, P.\u00a0Woelfel, 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\/780542.780634"},{"key":"9293_CR17","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Dodis, J.P. Steinberger, Domain extension for macs beyond the birthday barrier, in Advances in Cryptology\u2014EUROCRYPT 2011, pp. 323\u2013342 (2011)","DOI":"10.1007\/978-3-642-20465-4_19"},{"issue":"2","key":"9293_CR18","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00224-004-1195-x","volume":"38","author":"D Fotakis","year":"2005","unstructured":"D.\u00a0Fotakis, R.\u00a0Pagh, P.\u00a0Sanders, P.G. Spirakis, Space efficient hash tables with worst case constant access time. Theory Comput. Syst., 38(2), 229\u2013248 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"9293_CR19","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1137\/090770928","volume":"40","author":"AM Frieze","year":"2011","unstructured":"A.M. Frieze, P.\u00a0Melsted, M.\u00a0Mitzenmacher, An analysis of random-walk cuckoo hashing. SIAM J. Comput., 40(2), 291\u2013308 (2011)","journal-title":"SIAM J. Comput."},{"key":"9293_CR20","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, Towards a theory of software protection, in Advances in Cryptology\u2014CRYPTO \u201986, pp. 426\u2013439 (1986)","DOI":"10.1007\/3-540-47721-7_31"},{"key":"9293_CR21","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, S.\u00a0Goldwasser, S.\u00a0Micali, On the cryptographic applications of random functions, in Advances in Cryptology\u2014CRYPTO \u201984, pp. 276\u2013288 (1984)","DOI":"10.1007\/3-540-39568-7_22"},{"key":"9293_CR22","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, S.\u00a0Goldwasser, S.\u00a0Micali, How to construct random functions. J. ACM, 792\u2013807 (1986)","DOI":"10.1145\/6490.6503"},{"issue":"4","key":"9293_CR23","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1002\/rsa.20131","volume":"29","author":"J H\u00e5stad","year":"2006","unstructured":"J.\u00a0H\u00e5stad, The square lattice shuffle. Random Structures & Algorithms, 29(4), 466\u2013474 (2006)","journal-title":"Random Struct. Algorithms"},{"key":"9293_CR24","doi-asserted-by":"crossref","unstructured":"J.\u00a0H\u00e5stad, R.\u00a0Impagliazzo, L.A. Levin, M.\u00a0Luby, A pseudorandom generator from any one-way function. SIAM J. Comput., 1364\u20131396 (1999)","DOI":"10.1137\/S0097539793244708"},{"key":"9293_CR25","doi-asserted-by":"crossref","unstructured":"V.T. Hoang, B.\u00a0Morris, P.\u00a0Rogaway, An enciphering scheme based on a card shuffle, in Advances in Cryptology\u2014CRYPTO 2012, pp. 1\u201313 (2012)","DOI":"10.1007\/978-3-642-32009-5_1"},{"key":"9293_CR26","doi-asserted-by":"crossref","unstructured":"A.\u00a0Jain, K.\u00a0Pietrzak, A.\u00a0Tentes, Hardness preserving constructions of pseudorandom functions, in Theory of Cryptography, 9th Theory of Cryptography Conference, TCC 2012, pp. 369\u2013382 (2012)","DOI":"10.1007\/978-3-642-28914-9_21"},{"key":"9293_CR27","doi-asserted-by":"crossref","unstructured":"D.\u00a0Jetchev, O.\u00a0\u00d6zen, M.\u00a0Stam, Understanding adaptivity: Random systems revisited, in Advances in Cryptology \u2013 ASIACRYPT 2012, pp. 313\u2013330 (2012)","DOI":"10.1007\/978-3-642-34961-4_20"},{"issue":"1","key":"9293_CR28","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00453-008-9267-y","volume":"55","author":"E Kaplan","year":"2009","unstructured":"E.\u00a0Kaplan, M.\u00a0Naor, O.\u00a0Reingold, Derandomized constructions of k-wise (almost) independent permutations. Algorithmica 55(1), 113\u2013133 (2009)","journal-title":"Algorithmica"},{"issue":"4","key":"9293_CR29","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1137\/080728743","volume":"39","author":"A Kirsch","year":"2009","unstructured":"A.\u00a0Kirsch, M.\u00a0Mitzenmacher, U.\u00a0Wieder, More robust hashing: Cuckoo hashing with a stash. SIAM J. Comput., 39(4), 1543\u20131561 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9293_CR30","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"LA Levin","year":"1987","unstructured":"L.A. Levin, One-way functions and pseudorandom generators. Combinatorica, 7(4), 357\u2013363 (1987)","journal-title":"Combinatorica"},{"key":"9293_CR31","doi-asserted-by":"crossref","DOI":"10.1515\/9780691206844","volume-title":"Pseudorandomness and cryptographic applications. Princeton computer science notes","author":"M Luby","year":"1996","unstructured":"M.\u00a0Luby, Pseudorandomness and cryptographic applications. Princeton computer science notes. (Princeton University Press, 1996)"},{"issue":"2","key":"9293_CR32","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/0217022","volume":"17","author":"M Luby","year":"1988","unstructured":"M.\u00a0Luby, C.\u00a0Rackoff, How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2), 373\u2013386 (1988)","journal-title":"SIAM J. Comput."},{"key":"9293_CR33","doi-asserted-by":"crossref","unstructured":"U.M. Maurer, Indistinguishability of random systems, in Advances in Cryptology\u2014EUROCRYPT 2002, pp. 110\u2013132 (2002)","DOI":"10.1007\/3-540-46035-7_8"},{"key":"9293_CR34","doi-asserted-by":"crossref","unstructured":"U.M. Maurer, K.\u00a0Pietrzak, Composition of random systems: When two weak make one strong, in Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, pp. 410\u2013427 (2004)","DOI":"10.1007\/978-3-540-24638-1_23"},{"key":"9293_CR35","doi-asserted-by":"crossref","unstructured":"U.M. Maurer, S.\u00a0Tessaro, Domain extension of public random functions: Beyond the birthday barrier, in Advances in Cryptology\u2014CRYPTO 2007, pp. 187\u2013204 (2007)","DOI":"10.1007\/978-3-540-74143-5_11"},{"key":"9293_CR36","doi-asserted-by":"crossref","unstructured":"B.\u00a0Morris, P.\u00a0Rogaway, Sometimes-recurse shuffle - almost-random permutations in logarithmic expected time, in Advances in Cryptology\u2014EUROCRYPT 2014, pp. 311\u2013326 (2014)","DOI":"10.1007\/978-3-642-55220-5_18"},{"key":"9293_CR37","doi-asserted-by":"crossref","unstructured":"B.\u00a0Morris, P.\u00a0Rogaway, T.\u00a0Stegers, How to encipher messages on a small domain, in Advances in Cryptology\u2014CRYPTO 2009, pp. 286\u2013302 (2009)","DOI":"10.1007\/978-3-642-03356-8_17"},{"key":"9293_CR38","doi-asserted-by":"crossref","unstructured":"S.\u00a0Myers, Black-box composition does not imply adaptive security, in Advances in Cryptology\u2014EUROCRYPT 2004, pp. 189\u2013206 (2004)","DOI":"10.1007\/978-3-540-24676-3_12"},{"key":"9293_CR39","doi-asserted-by":"crossref","unstructured":"M.\u00a0Nandi, A unified method for improving prf bounds for a class of blockcipher based macs, in Fast Software Encryption, 17th International Workshop, FSE 2010, Seoul, Korea, pp. 212\u2013229 (2010)","DOI":"10.1007\/978-3-642-13858-4_12"},{"issue":"1","key":"9293_CR40","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/PL00003817","volume":"12","author":"M Naor","year":"1999","unstructured":"M.\u00a0Naor, O.\u00a0Reingold, On the construction of pseudorandom permutations: Luby-rackoff revisited. Journal of Cryptology, 12(1), 29\u201366 (1999a)","journal-title":"J. Cryptol."},{"issue":"2","key":"9293_CR41","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1006\/jcss.1998.1618","volume":"58","author":"M Naor","year":"1999","unstructured":"M.\u00a0Naor, O.\u00a0Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions. Journal of Computer and System Sciences, 58(2), 336\u2013375 (1999b)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9293_CR42","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s00145-001-0008-5","volume":"15","author":"M Naor","year":"2002","unstructured":"M.\u00a0Naor, O.\u00a0Reingold, Constructing pseudo-random permutations with a prescribed structure. Journal of Cryptology, 15(2), 97\u2013102, (2002)","journal-title":"J. Cryptol."},{"key":"9293_CR43","unstructured":"R.\u00a0Ostrovsky, An efficient software protection scheme, in Advances in Cryptology\u2014CRYPTO \u201989 (1989)"},{"issue":"1","key":"9293_CR44","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1137\/060658400","volume":"38","author":"A Pagh","year":"2008","unstructured":"A.\u00a0Pagh, R.\u00a0Pagh, Uniform hashing in constant time and optimal space. SIAM Journal on Computing, 38(1), 85\u201396, (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9293_CR45","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R Pagh","year":"2004","unstructured":"R.\u00a0Pagh, F.F. Rodler, Cuckoo hashing. J. Algorithms, 51 (2), 122\u2013144, (2004)","journal-title":"J. Algorithms"},{"key":"9293_CR46","doi-asserted-by":"crossref","unstructured":"J.\u00a0Patarin, Security of random feistel schemes with 5 or more rounds, in Advances in Cryptology\u2014CRYPTO 2004, pp. 106\u2013122 (2004)","DOI":"10.1007\/978-3-540-28628-8_7"},{"key":"9293_CR47","unstructured":"J.\u00a0Patarin, A proof of security in o(2 $$^{\\text{n}}$$ n ) for the benes scheme, in Progress in Cryptology\u2014 AFRICACRYPT 2008, pp. 209\u2013220 (2008)"},{"key":"9293_CR48","first-page":"293","volume":"2010","author":"J Patarin","year":"2010","unstructured":"J.\u00a0Patarin, Security of balanced and unbalanced feistel schemes with linear non equalities. IACR Cryptology ePrint Archive, 2010, 293 (2010).","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"9293_CR49","doi-asserted-by":"crossref","unstructured":"K.\u00a0Pietrzak, Composition does not imply adaptive security, in Advances in Cryptology\u2014CRYPTO 2005, pp. 55\u201365 (2005)","DOI":"10.1007\/11535218_4"},{"key":"9293_CR50","doi-asserted-by":"crossref","unstructured":"K.\u00a0Pietrzak, Composition implies adaptive security in minicrypt, in Advances in Cryptology\u2014EUROCRYPT 2006, pp. 328\u2013338 (2006)","DOI":"10.1007\/11761679_20"},{"issue":"3","key":"9293_CR51","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/2220357.2220361","volume":"59","author":"M P\u01cetra\u015fcu","year":"2012","unstructured":"M.\u00a0P\u01cetra\u015fcu, M.\u00a0Thorup, The power of simple tabulation hashing. J. ACM, 59(3), 14, (2012)","journal-title":"J. ACM"},{"key":"9293_CR52","doi-asserted-by":"crossref","unstructured":"T.\u00a0Ristenpart, S.\u00a0Yilek, The mix-and-cut shuffle: Small-domain encryption secure against N queries, in Advances in Cryptology\u2014CRYPTO 2013, pp. 392\u2013409 (2013)","DOI":"10.1007\/978-3-642-40041-4_22"},{"issue":"3","key":"9293_CR53","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0097539701386216","volume":"33","author":"A Siegel","year":"2004","unstructured":"A.\u00a0Siegel, On universal classes of extremely random constant-time hash functions. SIAM Journal on Computing, 33(3), 505\u2013543, (2004)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9293_CR54","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","volume":"22","author":"MN Wegman","year":"1981","unstructured":"M.N. Wegman, L.\u00a0Carter, New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci., 22 (3), 265\u2013279, (1981)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-018-9293-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-018-9293-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-018-9293-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T09:23:52Z","timestamp":1751621032000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-018-9293-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,7]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["9293"],"URL":"https:\/\/doi.org\/10.1007\/s00145-018-9293-0","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"type":"print","value":"0933-2790"},{"type":"electronic","value":"1432-1378"}],"subject":[],"published":{"date-parts":[[2018,5,7]]},"assertion":[{"value":"20 October 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}