{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T18:10:03Z","timestamp":1746295803227,"version":"3.40.4"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319087825"},{"type":"electronic","value":"9783319087832"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08783-2_18","type":"book-chapter","created":{"date-parts":[[2014,7,5]],"date-time":"2014-07-05T14:04:30Z","timestamp":1404569070000},"page":"203-214","source":"Crossref","is-referenced-by-count":1,"title":["A New View on Worst-Case to Average-Case Reductions for NP Problems"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Holenstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robin","family":"K\u00fcnzler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: On basing one-way functions on np-hardness. In: Kleinberg, J.M. (ed.) STOC, pp. 701\u2013710. ACM (2006), See also errata on author\u2019s webpage: http:\/\/www.wisdom.weizmann.ac.il\/~oded\/p_aggm.html","DOI":"10.1145\/1132516.1132614"},{"issue":"3","key":"18_CR2","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0022-0000(91)90006-Q","volume":"42","author":"W. Aiello","year":"1991","unstructured":"Aiello, W., H\u00e5stad, J.: Statistical zero-knowledge languages can be recognized in two rounds. J. Comput. Syst. Sci.\u00a042(3), 327\u2013345 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Miller, G.L. (ed.) STOC, pp. 99\u2013108. ACM (1996)","DOI":"10.1145\/237814.237838"},{"issue":"2","key":"18_CR4","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0022-0000(92)90019-F","volume":"44","author":"S. Ben-David","year":"1992","unstructured":"Ben-David, S., Chor, B., Goldreich, O., Luby, M.: On the theory of average case complexity. J. Comput. Syst. Sci.\u00a044(2), 193\u2013219 (1992)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"18_CR5","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1145\/200836.200880","volume":"42","author":"M. Blum","year":"1995","unstructured":"Blum, M., Kannan, S.: Designing programs that check their work. J. ACM\u00a042(1), 269\u2013291 (1995)","journal-title":"J. ACM"},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-642-40041-4_7","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"A. Bogdanov","year":"2013","unstructured":"Bogdanov, A., Lee, C.H.: Limits of provable security for homomorphic encryption. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol.\u00a08042, pp. 111\u2013128. Springer, Heidelberg (2013)"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehl\u00e9, D.: Classical hardness of learning with errors. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) STOC, pp. 575\u2013584. ACM (2013)","DOI":"10.1145\/2488608.2488680"},{"issue":"3","key":"18_CR8","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. J. Comput. Syst. Sci.\u00a047(3), 549\u2013595 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR9","unstructured":"Blum, M.: Designing programs to check their work. Technical Report 88-09, ICSI (1988)"},{"issue":"6","key":"18_CR10","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1109\/TIT.1983.1056754","volume":"29","author":"G. Brassard","year":"1983","unstructured":"Brassard, G.: Relativized cryptography. IEEE Transactions on Information Theory\u00a029(6), 877\u2013893 (1983)","journal-title":"IEEE Transactions on Information Theory"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Trevisan, L.: Average-case complexity. Foundations and Trends in Theoretical Computer Science\u00a02(1) (2006)","DOI":"10.1561\/0400000004"},{"issue":"4","key":"18_CR12","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1137\/S0097539705446974","volume":"36","author":"A. Bogdanov","year":"2006","unstructured":"Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. SIAM J. Comput.\u00a036(4), 1119\u20131159 (2006)","journal-title":"SIAM J. Comput."},{"key":"18_CR13","unstructured":"Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, June 9-12. IEEE Computer Society (2010)"},{"issue":"6","key":"18_CR14","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W. Diffie","year":"1976","unstructured":"Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Transactions on Information Theory\u00a022(6), 644\u2013654 (1976)","journal-title":"IEEE Transactions on Information Theory"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-10003-2_71","volume-title":"Automata, Languages and Programming","author":"S. Even","year":"1980","unstructured":"Even, S., Yacobi, Y.: Cryptocomplexity and NP-completeness. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol.\u00a085, pp. 195\u2013207. Springer, Heidelberg (1980)"},{"issue":"5","key":"18_CR16","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0222061","volume":"22","author":"J. Feigenbaum","year":"1993","unstructured":"Feigenbaum, J., Fortnow, L.: Random-self-reducibility of complete sets. SIAM J. Comput.\u00a022(5), 994\u20131005 (1993)","journal-title":"SIAM J. Comput."},{"key":"18_CR17","unstructured":"Goldreich, O., Goldwasser, S.: On the possibility of basing cryptography on the assumption that $\\text{P} \\neq \\textit{NP}$ , Unpublished manuscript (1998)"},{"key":"18_CR18","unstructured":"Goldreich, O.: Notes on levin\u2019s theory of average-case complexity. Electronic Colloquium on Computational Complexity (ECCC)\u00a04(58) (1997)"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: Hartmanis, J. (ed.) STOC, pp. 59\u201368. ACM (1986)","DOI":"10.1145\/12130.12137"},{"issue":"4","key":"18_CR20","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/s00037-007-0235-8","volume":"16","author":"D. Gutfreund","year":"2007","unstructured":"Gutfreund, D., Shaltiel, R., Ta-Shma, A.: If NP languages are hard on the worst-case, then it is easy to find their hard instances. Computational Complexity\u00a016(4), 412\u2013441 (2007)","journal-title":"Computational Complexity"},{"key":"18_CR21","doi-asserted-by":"crossref","unstructured":"Gutfreund, D., Ta-Shma, A.: Worst-case to average-case reductions revisited. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX and RANDOM 2007. LNCS, vol.\u00a04627, pp. 569\u2013583. Springer, Heidelberg (2007)","DOI":"10.1007\/978-3-540-74208-1_41"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Haitner, I., Mahmoody, M., Xiao, D.: A new sampling protocol and applications to basing cryptographic primitives on the hardness of NP. In: IEEE Conference on Computational Complexity [DBLP10], pp. 76\u201387","DOI":"10.1109\/CCC.2010.17"},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Levin, L.A.: No better ways to generate hard NP instances than picking uniformly at random. In: FOCS, pp. 812\u2013821. IEEE Computer Society (1990)","DOI":"10.1109\/FSCS.1990.89604"},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: A personal view of average-case complexity. In: Structure in Complexity Theory Conference, pp. 134\u2013147. IEEE Computer Society (1995)","DOI":"10.1109\/SCT.1995.514853"},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: Relativized separations of worst-case and average-case complexities for NP. In: IEEE Conference on Computational Complexity, pp. 104\u2013114. IEEE Computer Society (2011)","DOI":"10.1109\/CCC.2011.34"},{"issue":"4","key":"18_CR26","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1145\/356789.356792","volume":"11","author":"A. Lempel","year":"1979","unstructured":"Lempel, A.: Cryptology in transition. ACM Comput. Surv.\u00a011(4), 285\u2013303 (1979)","journal-title":"ACM Comput. Surv."},{"key":"18_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/978-3-642-03356-8_34","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"V. Lyubashevsky","year":"2009","unstructured":"Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 577\u2013594. Springer, Heidelberg (2009)"},{"issue":"1","key":"18_CR28","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1137\/S0097539703433511","volume":"34","author":"D. Micciancio","year":"2004","unstructured":"Micciancio, D.: Almost perfect lattices, the covering radius problem, and applications to Ajtai\u2019s connection factor. SIAM J. Comput.\u00a034(1), 118\u2013169 (2004)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"18_CR29","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/S0097539705447360","volume":"37","author":"D. Micciancio","year":"2007","unstructured":"Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput.\u00a037(1), 267\u2013302 (2007)","journal-title":"SIAM J. Comput."},{"key":"18_CR30","doi-asserted-by":"crossref","unstructured":"Mahmoody, M., Xiao, D.: On the power of randomized reductions and the checkability of sat. In: IEEE Conference on Computational Complexity [DBL10], pp. 64\u201375","DOI":"10.1109\/CCC.2010.16"},{"key":"18_CR31","doi-asserted-by":"crossref","unstructured":"Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract. In: Mitzenmacher, M. (ed.) STOC, pp. 333\u2013342. ACM (2009)","DOI":"10.1145\/1536414.1536461"},{"key":"18_CR32","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM\u00a056(6) (2009)","DOI":"10.1145\/1568318.1568324"},{"key":"18_CR33","doi-asserted-by":"crossref","unstructured":"Regev, O.: The learning with errors problem (invited survey). In: IEEE Conference on Computational Complexity [DBL10], pp. 191\u2013204 (2010)","DOI":"10.1109\/CCC.2010.26"},{"key":"18_CR34","unstructured":"Rubinfeld, R.: A mathematical theory of self-checking, self-testing and self-correcting programs. PhD thesis. UC Berkeley (1990)"},{"issue":"2","key":"18_CR35","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.P.: Pseudorandom generators without the xor lemma. J. Comput. Syst. Sci.\u00a062(2), 236\u2013266 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"18_CR36","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/2355580.2355583","volume":"4","author":"T. Watson","year":"2012","unstructured":"Watson, T.: Relativized worlds without worst-case to average-case reductions for NP. TOCT\u00a04(3), 8 (2012)","journal-title":"TOCT"},{"key":"18_CR37","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C.-K. Yap","year":"1983","unstructured":"Yap, C.-K.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci.\u00a026, 287\u2013300 (1983)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08783-2_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T17:49:14Z","timestamp":1746294554000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08783-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319087825","9783319087832"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08783-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}