{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:50Z","timestamp":1766281010545,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642289132"},{"type":"electronic","value":"9783642289149"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28914-9_27","type":"book-chapter","created":{"date-parts":[[2012,3,5]],"date-time":"2012-03-05T21:12:39Z","timestamp":1330981959000},"page":"476-493","source":"Crossref","is-referenced-by-count":13,"title":["Counterexamples to Hardness Amplification beyond Negligible"],"prefix":"10.1007","author":[{"given":"Yevgeniy","family":"Dodis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhishek","family":"Jain","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tal","family":"Moran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Wichs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/978-3-642-13190-5_6","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"J. Alwen","year":"2010","unstructured":"Alwen, J., Dodis, Y., Naor, M., Segev, G., Walfish, S., Wichs, D.: Public-Key Encryption in the Bounded-Retrieval Model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 113\u2013134. Springer, Heidelberg (2010)"},{"key":"27_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/978-3-642-03356-8_3","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"J. Alwen","year":"2009","unstructured":"Alwen, J., Dodis, Y., Wichs, D.: Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 36\u201354. Springer, Heidelberg (2009)"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Barak, B., Goldreich, O., Goldwasser, S., Lindell, Y.: Resettably-sound zero-knowledge and its applications. In: FOCS, pp. 116\u2013125 (2001)","DOI":"10.1109\/SFCS.2001.959886"},{"issue":"4","key":"27_CR4","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s00145-002-0116-x","volume":"15","author":"M. Bellare","year":"2002","unstructured":"Bellare, M.: A note on negligible functions. J. Cryptology\u00a015(4), 271\u2013284 (2002)","journal-title":"J. Cryptology"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Bellare, M., Impagliazzo, R., Naor, M.: Does parallel repetition lower the error in computationally sound protocols? In: FOCS, pp. 374\u2013383 (1997)","DOI":"10.1109\/SFCS.1997.646126"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable zero-knowledge (extended abstract). In: STOC, pp. 235\u2013244 (2000)","DOI":"10.1145\/335305.335334"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-540-30576-7_2","volume-title":"Theory of Cryptography","author":"R. Canetti","year":"2005","unstructured":"Canetti, R., Halevi, S., Steiner, M.: Hardness Amplification of Weakly Verifiable Puzzles. In: Kilian, J. (ed.) TCC 2005. LNCS, vol.\u00a03378, pp. 17\u201333. Springer, Heidelberg (2005)"},{"key":"27_CR8","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.: Amplifying Collision Resistance: A Complexity-Theoretic Treatment. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.\u00a04622, pp. 264\u2013283. Springer, Heidelberg (2007)"},{"key":"27_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/978-3-642-17373-8_16","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"K.-M. Chung","year":"2010","unstructured":"Chung, K.-M., Liu, F.-H., Lu, C.-J., Yang, B.-Y.: Efficient String-Commitment from Weak Bit-Commitment. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol.\u00a06477, pp. 268\u2013282. Springer, Heidelberg (2010)"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Deng, Y., Goyal, V., Sahai, A.: Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy. In: FOCS, pp. 251\u2013260 (2009)","DOI":"10.1109\/FOCS.2009.59"},{"key":"27_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/978-3-642-00457-5_9","volume-title":"Theory of Cryptography","author":"Y. Dodis","year":"2009","unstructured":"Dodis, Y., Impagliazzo, R., Jaiswal, R., Kabanets, V.: Security Amplification for Interactive Cryptographic Primitives. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 128\u2013145. Springer, Heidelberg (2009)"},{"key":"27_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-3-540-24676-3_21","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"C. Dwork","year":"2004","unstructured":"Dwork, C., Naor, M., Reingold, O.: Immunizing Encryption Schemes from Decryption Errors. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol.\u00a03027, pp. 342\u2013360. Springer, Heidelberg (2004)"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press (2001)","DOI":"10.1017\/CBO9780511546891"},{"key":"27_CR14","unstructured":"Goldreich, O., Nisan, N., Wigderson, A.: On Yao\u2019s XOR-Lemma. Electronic Colloquium on Computational Complexity (ECCC) 2(50) (1995)"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Goyal, V., Maji, H.K.: Stateless cryptographic protocols. In: FOCS (2011)","DOI":"10.1109\/FOCS.2011.74"},{"key":"27_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-642-01001-9_3","volume-title":"Advances in Cryptology - EUROCRYPT 2009","author":"V. Goyal","year":"2009","unstructured":"Goyal, V., Sahai, A.: Resettably Secure Computation. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol.\u00a05479, pp. 54\u201371. Springer, Heidelberg (2009)"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Haitner, I.: A parallel repetition theorem for any interactive argument. In: FOCS, pp. 241\u2013250 (2009)","DOI":"10.1109\/FOCS.2009.50"},{"key":"27_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/978-3-540-78524-8_34","volume-title":"Theory of Cryptography","author":"S. Halevi","year":"2008","unstructured":"Halevi, S., Rabin, T.: Degradation and Amplification of Computational Hardness. In: Canetti, R. (ed.) TCC 2008. LNCS, vol.\u00a04948, pp. 626\u2013643. Springer, Heidelberg (2008)"},{"key":"27_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-11799-2_1","volume-title":"Theory of Cryptography","author":"J. H\u00e5stad","year":"2010","unstructured":"H\u00e5stad, J., Pass, R., Wikstr\u00f6m, D., Pietrzak, K.: An Efficient Parallel Repetition Theorem. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol.\u00a05978, pp. 1\u201318. Springer, Heidelberg (2010)"},{"key":"27_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/978-3-540-74143-5_28","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"R. Impagliazzo","year":"2007","unstructured":"Impagliazzo, R., Jaiswal, R., Kabanets, V.: Chernoff-Type Direct Product Theorems. Journal of Cryptology (September 2008); In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.\u00a04622, pp. 500\u2013516. Springer, Heidelberg (2007)"},{"key":"27_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-642-19571-6_5","volume-title":"Theory of Cryptography","author":"A. Jain","year":"2011","unstructured":"Jain, A., Pietrzak, K.: Parallel Repetition for Leakage Resilience Amplification Revisited. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 58\u201369. Springer, Heidelberg (2011)"},{"key":"27_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-11799-2_3","volume-title":"Theory of Cryptography","author":"C.S. Jutla","year":"2010","unstructured":"Jutla, C.S.: Almost Optimal Bounds for Direct Product Threshold Theorem. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol.\u00a05978, pp. 37\u201351. Springer, Heidelberg (2010)"},{"key":"27_CR23","doi-asserted-by":"crossref","unstructured":"Lewko, A., Waters, B.: On the insecurity of parallel repetition for leakage resilience. In: FOCS, pp. 521\u2013530 (2010)","DOI":"10.1109\/FOCS.2010.57"},{"key":"27_CR24","doi-asserted-by":"crossref","unstructured":"Luby, M., Rackoff, C.: Pseudo-random permutation generators and cryptographic composition. In: STOC, pp. 356\u2013363 (1986)","DOI":"10.1145\/12130.12167"},{"key":"27_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/978-3-642-03356-8_21","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"U. Maurer","year":"2009","unstructured":"Maurer, U., Tessaro, S.: Computational Indistinguishability Amplification: Tight Product Theorems for System Composition. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 355\u2013373. Springer, Heidelberg (2009)"},{"key":"27_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-642-11799-2_15","volume-title":"Theory of Cryptography","author":"U. Maurer","year":"2010","unstructured":"Maurer, U., Tessaro, S.: A Hardcore Lemma for Computational Indistinguishability: Security Amplification for Arbitrarily Weak PRGs with Optimal Stretch. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol.\u00a05978, pp. 237\u2013254. Springer, Heidelberg (2010)"},{"key":"27_CR27","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/PL00003817","volume":"12","author":"M. Naor","year":"1999","unstructured":"Naor, M., Reingold, O.: On the construction of pseudo-random permutations: Luby-Rackoff revisited. J. of Cryptology\u00a012, 29\u201366 (1999); Preliminary version in: Proc. STOC 1997","journal-title":"J. of Cryptology"},{"key":"27_CR28","doi-asserted-by":"crossref","unstructured":"Pass, R., Venkitasubramaniam, M.: An efficient parallel repetition theorem for Arthur-Merlin games. In: STOC, pp. 420\u2013429 (2007)","DOI":"10.1145\/1250790.1250853"},{"key":"27_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-540-70936-7_5","volume-title":"Theory of Cryptography","author":"K. Pietrzak","year":"2007","unstructured":"Pietrzak, K., Wikstr\u00f6m, D.: Parallel Repetition of Computationally Sound Protocols Revisited. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol.\u00a04392, pp. 86\u2013102. Springer, Heidelberg (2007)"},{"key":"27_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-19571-6_3","volume-title":"Theory of Cryptography","author":"S. Tessaro","year":"2011","unstructured":"Tessaro, S.: Security Amplification for the Cascade of Arbitrarily Weak PRPs: Tight Bounds via the Interactive Hardcore Lemma. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 37\u201354. Springer, Heidelberg (2011)"},{"key":"27_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-74143-5_12","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"D. Unruh","year":"2007","unstructured":"Unruh, D.: Random Oracles and Auxiliary Input. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.\u00a04622, pp. 205\u2013223. Springer, Heidelberg (2007)"},{"key":"27_CR32","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Theory and applications of trapdoor functions (extended abstract). In: FOCS, 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-28914-9_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T12:03:54Z","timestamp":1742645034000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28914-9_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642289132","9783642289149"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28914-9_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}