{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:29:43Z","timestamp":1778128183553,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642227912","type":"print"},{"value":"9783642227929","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22792-9_26","type":"book-chapter","created":{"date-parts":[[2011,8,5]],"date-time":"2011-08-05T15:32:14Z","timestamp":1312558334000},"page":"465-484","source":"Crossref","is-referenced-by-count":127,"title":["Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions"],"prefix":"10.1007","author":[{"given":"Daniele","family":"Micciancio","sequence":"first","affiliation":[]},{"given":"Petros","family":"Mol","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/978-3-642-13190-5_28","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"S. Agrawal","year":"2010","unstructured":"Agrawal, S., Boneh, D., Boyen, X.: Efficient Lattice (H)IBE in the Standard Model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 553\u2013572. Springer, Heidelberg (2010)"},{"key":"26_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/978-3-642-14623-7_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"S. Agrawal","year":"2010","unstructured":"Agrawal, S., Boneh, D., Boyen, X.: Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 98\u2013115. Springer, Heidelberg (2010)"},{"key":"26_CR3","unstructured":"Akavia, A.: Learning Noisy Characters, Multiplication Codes and Hardcore Predicates. PhD thesis. MIT (February 2008)"},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Akavia, A., Goldwasser, S., Safra, S.: Proving Hard-Core Predicates Using List Decoding. In: FOCS, pp. 146\u2013157 (2003)","DOI":"10.1109\/SFCS.2003.1238189"},{"key":"26_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/978-3-642-00457-5_28","volume-title":"Theory of Cryptography","author":"A. Akavia","year":"2009","unstructured":"Akavia, A., Goldwasser, S., Vaikuntanathan, V.: Simultaneous Hardcore Bits and Cryptography against Memory Attacks. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 474\u2013495. Springer, Heidelberg (2009)"},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/978-3-642-03356-8_35","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"B. Applebaum","year":"2009","unstructured":"Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 595\u2013618. Springer, Heidelberg (2009)"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: ICALP (2011), http:\/\/www.eccc.uni-trier.de\/report\/2010\/066\/","DOI":"10.1007\/978-3-642-22006-7_34"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Blum, A., Furst, M.L., Jackson, J.C., Kearns, M.J., Mansour, Y., Rudich, S.: Weakly Learning DNF and Characterizing Statistical Query Learning using Fourier Analysis. In: STOC, pp. 253\u2013262 (1994)","DOI":"10.1145\/195058.195147"},{"key":"26_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/3-540-48329-2_24","volume-title":"Advances in Cryptology - CRYPTO \u201993","author":"A. Blum","year":"1994","unstructured":"Blum, A., Furst, M.L., Kearns, M. J., Lipton, R.J.: Cryptographic Primitives Based on Hard Learning Problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol.\u00a0773, pp. 278\u2013291. Springer, Heidelberg (1994)"},{"key":"26_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/978-3-642-13190-5_27","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"D. Cash","year":"2010","unstructured":"Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai Trees, or How to Delegate a Lattice Basis. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 523\u2013552. Springer, Heidelberg (2010)"},{"key":"26_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-642-11799-2_22","volume-title":"Theory of Cryptography","author":"Y. Dodis","year":"2010","unstructured":"Dodis, Y., Goldwasser, S., Tauman Kalai, Y., Peikert, C., Vaikuntanathan, V.: Public-Key Encryption Schemes with Auxiliary Inputs. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol.\u00a05978, pp. 361\u2013381. Springer, Heidelberg (2010)"},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/3-540-68339-9_22","volume-title":"Advances in Cryptology - EUROCRYPT \u201996","author":"J.-B. Fischer","year":"1996","unstructured":"Fischer, J.-B., Stern, J.: An efficient pseudo-random generator provably as secure as syndrome decoding. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol.\u00a01070, pp. 245\u2013255. Springer, Heidelberg (1996)"},{"key":"26_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1007\/978-3-642-13190-5_26","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"C. Gentry","year":"2010","unstructured":"Gentry, C., Halevi, S., Vaikuntanathan, V.: A Simple BGN-Type Cryptosystem from LWE. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 506\u2013522. Springer, Heidelberg (2010)"},{"key":"26_CR14","first-page":"197","volume-title":"STOC","author":"C. Gentry","year":"2008","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for Hard Lattices and New Cryptographic Constructions. In: STOC, pp. 197\u2013206. ACM, New York (2008)"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Levin, L.A.: A Hard-Core Predicate for All One-Way Functions. In: STOC, pp. 25\u201332 (1989)","DOI":"10.1145\/73007.73010"},{"key":"26_CR16","unstructured":"Goldwasser, S., Kalai, Y.T., Peikert, C., Vaikuntanathan, V.: Robustness of the Learning with Errors Assumption. In: ICS (2010)"},{"key":"26_CR17","first-page":"248","volume-title":"FOCS","author":"R. Impagliazzo","year":"1989","unstructured":"Impagliazzo, R., Zuckerman, D.: How to Recycle Random Bits. In: FOCS, pp. 248\u2013253. IEEE Computer Society, Washington, DC, USA (1989)"},{"issue":"4","key":"26_CR18","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s001459900012","volume":"9","author":"R. Impagliazzo","year":"1996","unstructured":"Impagliazzo, R., Naor, M.: Efficient Cryptographic Schemes Provably as Secure as Subset Sum. J. Cryptology\u00a09(4), 199\u2013216 (1996)","journal-title":"J. Cryptology"},{"issue":"3","key":"26_CR19","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00145-010-9061-2","volume":"23","author":"J. Katz","year":"2010","unstructured":"Katz, J., Shin, J.S., Smith, A.: Parallel and Concurrent Security of the HB and HB\u2009+\u2009 Protocols. J. Cryptology\u00a023(3), 402\u2013421 (2010)","journal-title":"J. Cryptology"},{"key":"26_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-540-71677-8_21","volume-title":"Public Key Cryptography \u2013 PKC 2007","author":"A. Kawachi","year":"2007","unstructured":"Kawachi, A., Tanaka, K., Xagawa, K.: Multi-bit cryptosystems based on lattice problems. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol.\u00a04450, pp. 315\u2013329. Springer, Heidelberg (2007)"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Mansour, Y.: Learning Decision Trees Using the Fourier Sprectrum. In: STOC, pp. 455\u2013464 (1991)","DOI":"10.1145\/103418.103466"},{"key":"26_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-19074-2_21","volume-title":"Topics in Cryptology \u2013 CT-RSA 2011","author":"R. Lindner","year":"2011","unstructured":"Lindner, R., Peikert, C.: Better Key Sizes (and Attacks) for LWE-Based Encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol.\u00a06558, pp. 319\u2013339. Springer, Heidelberg (2011)"},{"key":"26_CR23","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)"},{"key":"26_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-13190-5_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"V. Lyubashevsky","year":"2010","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: On Ideal Lattices and Learning with Errors over Rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 1\u201323. Springer, Heidelberg (2010)"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Micciancio, D.: Duality in Lattice Based Cryptography. In: Public Key Cryptography (2010) (invited talk)","DOI":"10.1007\/978-1-4419-5906-5_417"},{"key":"26_CR26","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-540-88702-7_5","volume-title":"Post Quantum Cryptography","author":"D. Micciancio","year":"2009","unstructured":"Micciancio, D., Regev, O.: Lattice-Based Cryptography. In: Post Quantum Cryptography, pp. 147\u2013191. Springer Publishing Company, Heidelberg (2009)"},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"Mossel, E., O\u2019Donnell, R., Servedio, R.A.: Learning Juntas. In: STOC, pp. 206\u2013212 (2003)","DOI":"10.1145\/780542.780574"},{"key":"26_CR28","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/1536414.1536461","volume-title":"STOC","author":"C. Peikert","year":"2009","unstructured":"Peikert, C.: Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem. In: STOC, pp. 333\u2013342. ACM, New York (2009)"},{"key":"26_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1007\/978-3-540-85174-5_31","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"C. Peikert","year":"2008","unstructured":"Peikert, C., Vaikuntanathan, V., Waters, B.: A Framework for Efficient and Composable Oblivious Transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 554\u2013571. Springer, Heidelberg (2008)"},{"key":"26_CR30","first-page":"187","volume-title":"STOC","author":"C. Peikert","year":"2008","unstructured":"Peikert, C., Waters, B.: Lossy Trapdoor Functions and Their Applications. In: STOC, pp. 187\u2013196. ACM, New York (2008)"},{"issue":"6","key":"26_CR31","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O. Regev","year":"2009","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. Journal of ACM\u00a056(6), 34 (2009); Preliminary version in STOC 2005","journal-title":"Journal of ACM"},{"key":"26_CR32","doi-asserted-by":"crossref","unstructured":"Regev, O.: The Learning with Errors Problem (Invited Survey). In: IEEE Conference on Computational Complexity, pp. 191\u2013204 (2010)","DOI":"10.1109\/CCC.2010.26"},{"key":"26_CR33","unstructured":"R\u00fcckert, M., Schneider, M.: Estimating the Security of Lattice-based Cryptosystems. Technical Report 2010\/137, IACR ePrint archive (2010)"},{"key":"26_CR34","unstructured":"Stefankovic, D.: Fourier Transform in Computer Science. Master\u2019s thesis, University of Chicago (October 2000)"},{"key":"26_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-642-10366-7_36","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"D. Stehl\u00e9","year":"2009","unstructured":"Stehl\u00e9, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient Public Key Encryption Based on Ideal Lattices. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.\u00a05912, pp. 617\u2013635. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22792-9_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:08:40Z","timestamp":1606187320000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22792-9_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642227912","9783642227929"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22792-9_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}