{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T17:35:50Z","timestamp":1794418550681,"version":"4.9.1"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642290107","type":"print"},{"value":"9783642290114","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29011-4_42","type":"book-chapter","created":{"date-parts":[[2012,4,5]],"date-time":"2012-04-05T03:05:53Z","timestamp":1333595153000},"page":"719-737","source":"Crossref","is-referenced-by-count":362,"title":["Pseudorandom Functions and Lattices"],"prefix":"10.1007","author":[{"given":"Abhishek","family":"Banerjee","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chris","family":"Peikert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alon","family":"Rosen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"42_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":"42_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":"42_CR3","first-page":"1","volume":"13","author":"M. Ajtai","year":"2004","unstructured":"Ajtai, M.: Generating hard instances of lattice problems. Quaderni di Matematica\u00a013, 1\u201332 (2004); Preliminary version in STOC 1996","journal-title":"Quaderni di Matematica"},{"key":"42_CR4","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":"42_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-22006-7_34","volume-title":"Automata, Languages and Programming","author":"S. Arora","year":"2011","unstructured":"Arora, S., Ge, R.: New Algorithms for Learning in Presence of Errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 403\u2013415. Springer, Heidelberg (2011)"},{"key":"42_CR6","unstructured":"Banerjee, A., Ben-Zvi, N., Peikert, C., Rosen, A.: SPRINT: Efficient pseudorandomness via rounded integer products (2011) (manuscript)"},{"key":"42_CR7","unstructured":"Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. Cryptology ePrint Archive, Report 2011\/401 (2011), \n                    \n                      http:\/\/eprint.iacr.org\/"},{"issue":"4","key":"42_CR8","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A. Blum","year":"2003","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM\u00a050(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Boneh, D., Montgomery, H.W., Raghunathan, A.: Algebraic pseudorandom functions with improved efficiency from the augmented cascade. In: ACM Conference on Computer and Communications Security, pp. 131\u2013140 (2010)","DOI":"10.1145\/1866307.1866323"},{"key":"42_CR10","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Gentry, C., Vaikuntanathan, V.: Fully homomorphic encryption without bootstrapping. Cryptology ePrint Archive, Report 2011\/277 (2011), \n                    \n                      http:\/\/eprint.iacr.org\/","DOI":"10.1145\/2090236.2090262"},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: FOCS, pp. 97\u2013106 (2011)","DOI":"10.1109\/FOCS.2011.12"},{"key":"42_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/978-3-642-22792-9_29","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"Z. Brakerski","year":"2011","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.\u00a06841, pp. 505\u2013524. Springer, Heidelberg (2011)"},{"key":"42_CR13","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":"42_CR14","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169\u2013178 (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197\u2013206 (2008)","DOI":"10.1145\/1374376.1374407"},{"issue":"4","key":"42_CR16","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\u00a033(4), 792\u2013807 (1986); Preliminary version in FOCS 1984","journal-title":"J. ACM"},{"key":"42_CR17","unstructured":"Goldwasser, S., Kalai, Y.T., Peikert, C., Vaikuntanathan, V.: Robustness of the learning with errors assumption. In: ICS, pp. 230\u2013240 (2010)"},{"key":"42_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-45682-1_4","volume-title":"Advances in Cryptology - ASIACRYPT 2001","author":"N.J. Hopper","year":"2001","unstructured":"Hopper, N.J., Blum, M.: Secure Human Identification Protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol.\u00a02248, pp. 52\u201366. Springer, Heidelberg (2001)"},{"key":"42_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/11535218_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"A. Juels","year":"2005","unstructured":"Juels, A., Weis, S.A.: Authenticating Pervasive Devices with Human Protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol.\u00a03621, pp. 293\u2013308. Springer, Heidelberg (2005)"},{"issue":"3","key":"42_CR20","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\n                    \n                      \n                    \n                    $^{\\mbox{+}}$\n                   protocols. J. Cryptology\u00a023(3), 402\u2013421 (2010); Preliminary version in Eurocrypt 2006","journal-title":"J. Cryptology"},{"key":"42_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/978-3-642-20465-4_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"E. Kiltz","year":"2011","unstructured":"Kiltz, E., Pietrzak, K., Cash, D., Jain, A., Venturi, D.: Efficient Authentication from Hard Learning Problems. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol.\u00a06632, pp. 7\u201326. Springer, Heidelberg (2011)"},{"issue":"4","key":"42_CR22","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A.K. Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra Jr., H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen\u00a0261(4), 515\u2013534 (1982)","journal-title":"Mathematische Annalen"},{"key":"42_CR23","doi-asserted-by":"crossref","unstructured":"Lewko, A.B., Waters, B.: Efficient pseudorandom functions from the decisional linear assumption and weaker variants. In: ACM Conference on Computer and Communications Security, pp. 112\u2013120 (2009)","DOI":"10.1145\/1653662.1653677"},{"key":"42_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-540-71039-4_4","volume-title":"Fast Software Encryption","author":"V. Lyubashevsky","year":"2008","unstructured":"Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: A Modest Proposal for FFT Hashing. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol.\u00a05086, pp. 54\u201372. Springer, Heidelberg (2008)"},{"key":"42_CR25","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":"42_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/978-3-642-22792-9_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"D. Micciancio","year":"2011","unstructured":"Micciancio, D., Mol, P.: Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.\u00a06841, pp. 465\u2013484. Springer, Heidelberg (2011)"},{"key":"42_CR27","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1007\/978-3-642-29011-4_41","volume-title":"EUROCRYPT 2012","author":"D. Micciancio","year":"2012","unstructured":"Micciancio, D., Peikert, C.: Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol.\u00a07237, pp. 700\u2013718. Springer, Heidelberg (2012)"},{"issue":"2","key":"42_CR28","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1006\/jcss.1998.1618","volume":"58","author":"M. Naor","year":"1999","unstructured":"Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of pseudo-random functions. J. Comput. Syst. Sci.\u00a058(2), 336\u2013375 (1999); Preliminary version in FOCS 1995","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"42_CR29","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/972639.972643","volume":"51","author":"M. Naor","year":"2004","unstructured":"Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. J. ACM\u00a051(2), 231\u2013262 (2004); Preliminary version in FOCS 1997","journal-title":"J. ACM"},{"issue":"5","key":"42_CR30","doi-asserted-by":"publisher","first-page":"1383","DOI":"10.1137\/S0097539701389257","volume":"31","author":"M. Naor","year":"2002","unstructured":"Naor, M., Reingold, O., Rosen, A.: Pseudorandom functions and factoring. SIAM J. Comput.\u00a031(5), 1383\u20131404 (2002); Preliminary version in STOC 2000","journal-title":"SIAM J. Comput."},{"key":"42_CR31","doi-asserted-by":"crossref","unstructured":"Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: STOC, pp. 333\u2013342 (2009)","DOI":"10.1145\/1536414.1536461"},{"key":"42_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/978-3-642-14623-7_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"C. Peikert","year":"2010","unstructured":"Peikert, C.: An Efficient and Parallel Gaussian Sampler for Lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 80\u201397. Springer, Heidelberg (2010)"},{"key":"42_CR33","doi-asserted-by":"crossref","unstructured":"Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: STOC, pp. 187\u2013196 (2008)","DOI":"10.1145\/1374376.1374406"},{"key":"42_CR34","unstructured":"Pietrzak, K.: Subspace LWE (2010) (manuscript), \n                    \n                      http:\/\/homepages.cwi.nl\/~pietrzak\/publications\/SLWE.pdf\n                    \n                    \n                   (Last retrieved from June 28, 2011)"},{"issue":"6","key":"42_CR35","doi-asserted-by":"publisher","first-page":"1","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. J. ACM\u00a056(6), 1\u201340 (2009); Preliminary version in STOC 2005","journal-title":"J. ACM"},{"issue":"5","key":"42_CR36","doi-asserted-by":"publisher","first-page":"896","DOI":"10.1137\/0221053","volume":"21","author":"J.H. Reif","year":"1992","unstructured":"Reif, J.H., Tate, S.R.: On threshold circuits and polynomial computation. SIAM J. Comput.\u00a021(5), 896\u2013908 (1992)","journal-title":"SIAM J. Comput."},{"key":"42_CR37","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"C.-P. Schnorr","year":"1987","unstructured":"Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci.\u00a053, 201\u2013224 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"42_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-13190-5_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"M. Dijk van","year":"2010","unstructured":"van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully Homomorphic Encryption over the Integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 24\u201343. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29011-4_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T07:18:46Z","timestamp":1620112726000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29011-4_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642290107","9783642290114"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29011-4_42","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-642-29011-4","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}