{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:55Z","timestamp":1763468035209,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642195709"},{"type":"electronic","value":"9783642195716"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19571-6_1","type":"book-chapter","created":{"date-parts":[[2011,3,22]],"date-time":"2011-03-22T12:04:42Z","timestamp":1300795482000},"page":"1-18","source":"Crossref","is-referenced-by-count":4,"title":["Input Locality and Hardness Amplification"],"prefix":"10.1007","author":[{"given":"Andrej","family":"Bogdanov","sequence":"first","affiliation":[]},{"given":"Alon","family":"Rosen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. John Wiley, Chichester (1992)"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: STOC 2010, pp. 171\u2013180 (2010)","DOI":"10.1145\/1806689.1806715"},{"key":"1_CR3","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. In: FOCS 2004, pp. 166\u2013175 (2004)"},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-540-74143-5_6","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"B. Applebaum","year":"2007","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography with Constant Input Locality. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.\u00a04622, pp. 92\u2013110. Springer, Heidelberg (2007); Journal version in J. Cryptology 22(4), 429-469 (2009)"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: STOC 2000, pp. 435\u2013440 (2000)","DOI":"10.1145\/335305.335355"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/978-3-642-03685-9_30","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Bogdanov","year":"2009","unstructured":"Bogdanov, A., Qiao, Y.: On the security of goldreich\u2019s one-way function. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 392\u2013405. Springer, Heidelberg (2009)"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-3-642-00457-5_31","volume-title":"Theory of Cryptography","author":"J. Cook","year":"2009","unstructured":"Cook, J., Etesami, O., Miller, R., Trevisan, L.: Goldreich\u2019s One-Way Function Candidate and Myopic Backtracking Algorithms. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 521\u2013538. Springer, Heidelberg (2009)"},{"key":"1_CR8","unstructured":"Goldreich, O.: Candidate One-Way Functions Based on Expander Graphs. Electronic Colloquium on Computational Complexity (ECCC) 7(90) (2000)"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Impagliazzo, R., Levin, L.A., Venkatesan, R., Zuckerman, D.: Security Preserving Amplification of Hardness. In: FOCS 1990, pp. 318\u2013326 (1990)","DOI":"10.1109\/FSCS.1990.89550"},{"issue":"6","key":"1_CR10","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1137\/0222069","volume":"22","author":"O. Goldreich","year":"1993","unstructured":"Goldreich, O., Krawczyk, H., Luby, M.: On the Existence of Pseudorandom Generators. SIAM J. Comput.\u00a022(6), 1163\u20131175 (1993)","journal-title":"SIAM J. Comput."},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/11818175_2","volume-title":"Advances in Cryptology - CRYPTO 2006","author":"I. Haitner","year":"2006","unstructured":"Haitner, I., Harnik, D., Reingold, O.: On the Power of the Randomized Iterate. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol.\u00a04117, pp. 22\u201340. Springer, Heidelberg (2006)"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Levin, L., Luby, M.: Pseudo-random Generation from One-way Functions. In: STOC 1989, pp. 12\u201324 (1989)","DOI":"10.1145\/73007.73009"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Luby, M.: One-way Functions are Essential for Complexity Based Cryptography. In: FOCS 1989, pp. 230\u2013235 (1989)","DOI":"10.1109\/SFCS.1989.63483"},{"issue":"1","key":"1_CR14","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0304-3975(93)90257-T","volume":"107","author":"Y. Mansour","year":"1993","unstructured":"Mansour, Y., Nisan, N., Tiwari, P.: The Computational Complexity of Universal Hashing. Theor. Comput. Sci.\u00a0107(1), 121\u2013133 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-540-30576-7_3","volume-title":"Theory of Cryptography","author":"H.C. Lin","year":"2005","unstructured":"Lin, H.C., Trevisan, L., Wee, H.: On Hardness Amplification of One-Way Functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol.\u00a03378, pp. 34\u201349. Springer, Heidelberg (2005)"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Theory and Applications of Trapdoor Functions (Extended Abstract). In: FOCS 1982, pp. 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"}],"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-19571-6_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T16:56:47Z","timestamp":1741107407000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19571-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642195709","9783642195716"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19571-6_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}