{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T04:03:33Z","timestamp":1746504213174,"version":"3.40.4"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319130385"},{"type":"electronic","value":"9783319130392"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"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":[[2014]]},"DOI":"10.1007\/978-3-319-13039-2_6","type":"book-chapter","created":{"date-parts":[[2014,10,24]],"date-time":"2014-10-24T19:36:19Z","timestamp":1414179379000},"page":"89-103","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions"],"prefix":"10.1007","author":[{"given":"Nishanth","family":"Chandran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjam","family":"Garg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,25]]},"reference":[{"issue":"3","key":"6_CR1","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Random Struct. Algorithms 3(3), 289\u2013304 (1992)","journal-title":"Random Struct. Algorithms"},{"key":"6_CR2","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. 7194, pp. 357\u2013368. Springer, Heidelberg (2012)"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Berman, I., Haitner, I., Komargodski, I., Naor, M.: Hardness preserving reductions via cuckoo hashing. IACR Cryptology ePrint Archive 2012: 722 (2012)","DOI":"10.1007\/978-3-642-36594-2_3"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-36594-2_3","volume-title":"Theory of Cryptography","author":"I Berman","year":"2013","unstructured":"Berman, I., Haitner, I., Komargodski, I., Naor, M.: Hardness preserving reductions via cuckoo hashing. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 40\u201359. Springer, Heidelberg (2013)"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, November 3-5, pp. 112\u2013117 (1982)","DOI":"10.1109\/SFCS.1982.72"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Carter, L., Wegman, M.N.: Universal classes of hash functions (extended abstract). In: Proceedings of the 9th Annual ACM Symposium on Theory of Computing, Boulder, Colorado, USA, May 4-6, pp. 106\u2013112 (1977)","DOI":"10.1145\/800105.803400"},{"key":"6_CR7","unstructured":"Chandran, N., Garg, S.: Hardness preserving constructions of pseudorandom functions, revisited. IACR Cryptology ePrint Archive 2012: 616 (2012)"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/978-3-642-14623-7_24","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"C Cho","year":"2010","unstructured":"Cho, C., Lee, C.-K., Ostrovsky, R.: Equivalence of uniform key agreement and composition insecurity. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 447\u2013464. Springer, Heidelberg (2010)"},{"key":"6_CR9","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. 263, pp. 426\u2013439. Springer, Heidelberg (1987)"},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/3-540-47721-7_8","volume-title":"Advances in Cryptology - CRYPTO \u201986","author":"O Goldreich","year":"1987","unstructured":"Goldreich, O.: Two remarks concerning the goldwasser-micali-rivest signature scheme. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 104\u2013110. Springer, Heidelberg (1987)"},{"key":"6_CR11","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. 196, pp. 276\u2013288. Springer, Heidelberg (1985)"},{"issue":"4","key":"6_CR12","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"key":"6_CR13","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. 7194, pp. 369\u2013382. Springer, Heidelberg (2012)"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/3-540-69053-0_28","volume-title":"Advances in Cryptology - EUROCRYPT \u201997","author":"K Kurosawa","year":"1997","unstructured":"Kurosawa, K., Johansson, T., Stinson, D.R.: Almost $$k$$-wise independent sample spaces and their cryptologic applications. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 409\u2013421. Springer, Heidelberg (1997)"},{"issue":"4","key":"6_CR15","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"LA Levin","year":"1987","unstructured":"Levin, L.A.: One-way functions and pseudorandom generators. Combinatorica 7(4), 357\u2013363 (1987)","journal-title":"Combinatorica"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Luby, M.: Pseudorandomness and cryptographic applications. Princeton computer science notes. Princeton University Press (1996)","DOI":"10.1515\/9780691206844"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/3-540-48184-2_34","volume-title":"Advances in Cryptology - CRYPTO \u201987","author":"M Luby","year":"1988","unstructured":"Luby, M., Rackoff, C.: A study of password security. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 392\u2013397. Springer, Heidelberg (1988)"},{"key":"6_CR18","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":"UM Maurer","year":"2002","unstructured":"Maurer, U.M.: Indistinguishability of random systems. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 110\u2013133. Springer, Heidelberg (2002)"},{"key":"6_CR19","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. 3027, pp. 189\u2013206. Springer, Heidelberg (2004)"},{"issue":"4","key":"6_CR20","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput. 22(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of psuedo-random functions. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, October 23-25, pp. 170\u2013181 (1995)","DOI":"10.1109\/SFCS.1995.492474"},{"key":"6_CR22","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. 3621, pp. 55\u201365. Springer, Heidelberg (2005)"},{"key":"6_CR23","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. 4004, pp. 328\u2013338. Springer, Heidelberg (2006)"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Wegman, M.N., Carter, L.: New classes and applications of hash functions. In: 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 29-31, pp. 175\u2013182 (1979)","DOI":"10.1109\/SFCS.1979.26"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Theory and applications of trapdoor functions (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, November 3-5, pp. 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","Progress in Cryptology -- INDOCRYPT 2014"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13039-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T13:14:41Z","timestamp":1746450881000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13039-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319130385","9783319130392"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13039-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"25 October 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}