{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T18:38:45Z","timestamp":1784831925547,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":47,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642033551","type":"print"},{"value":"9783642033568","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03356-8_35","type":"book-chapter","created":{"date-parts":[[2009,8,18]],"date-time":"2009-08-18T14:00:39Z","timestamp":1250604039000},"page":"595-618","source":"Crossref","is-referenced-by-count":401,"title":["Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems"],"prefix":"10.1007","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Cash","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chris","family":"Peikert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amit","family":"Sahai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"35_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/11555827_22","volume-title":"Computer Security \u2013 ESORICS 2005","author":"P. Ad\u00e3o","year":"2005","unstructured":"Ad\u00e3o, P., Bana, G., Herzog, J., Scedrov, A.: Soundness of formal encryption in the presence of key-cycles. In: de Capitani di Vimercati, S., Syverson, P.F., Gollmann, D. (eds.) ESORICS 2005. LNCS, vol.\u00a03679, pp. 374\u2013396. Springer, Heidelberg (2005)"},{"key":"35_CR2","unstructured":"Albrecht, M., Bard, G., Hart, W.: Efficient multiplication of dense matrices over gf(2). CoRR, abs\/0811.1714 (2008)"},{"key":"35_CR3","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: Proc. 44th FOCS, pp. 298\u2013307 (2003)","DOI":"10.1109\/SFCS.2003.1238204"},{"issue":"4","key":"35_CR4","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B. Applebaum","year":"2006","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. SIAM J. Comput.\u00a036(4), 845\u2013888 (2006); Preliminary version in Proc.\u00a045th FOCS (2004)","journal-title":"SIAM J. Comput."},{"key":"35_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/11830924_25","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"B. Applebaum","year":"2006","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: On pseudorandom generators with linear stretch in NC0. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, pp. 260\u2013271. Springer, Heidelberg (2006)"},{"key":"35_CR6","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); full version in, http:\/\/www.cs.princeton.edu\/~bappelba\/pubs\/input-locality-full.pdf"},{"key":"35_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1007\/978-3-540-89255-7_31","volume-title":"Advances in Cryptology - ASIACRYPT 2008","author":"M. Backes","year":"2008","unstructured":"Backes, M., D\u00fcrmuth, M., Unruh, D.: OAEP is secure under key-dependent messages. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol.\u00a05350, pp. 506\u2013523. Springer, Heidelberg (2008)"},{"key":"35_CR8","doi-asserted-by":"crossref","unstructured":"Backes, M., Pfitzmann, B., Scedrov, A.: Key-dependent message security under active attacks - BRSIM\/UC-soundness of symbolic encryption with key cycles. In: CSF, pp. 112\u2013124 (2007)","DOI":"10.1109\/CSF.2007.23"},{"key":"35_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/3-540-36492-7_6","volume-title":"Selected Areas in Cryptography","author":"J. Black","year":"2003","unstructured":"Black, J., Rogaway, P., Shrimpton, T.: Encryption-scheme security in the presence of key-dependent messages. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol.\u00a02595, pp. 62\u201375. Springer, Heidelberg (2003)"},{"key":"35_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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)"},{"issue":"4","key":"35_CR11","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":"35_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1109\/FCCM.2006.12","volume-title":"FCCM 2006: Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines","author":"A. Bogdanov","year":"2006","unstructured":"Bogdanov, A., Mertens, M.C.: A parallel hardware architecture for fast gaussian elimination over gf(2). In: FCCM 2006: Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, Washington, DC, USA, pp. 237\u2013248. IEEE Computer Society, Los Alamitos (2006)"},{"key":"35_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-85174-5_7","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"D. Boneh","year":"2008","unstructured":"Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-secure encryption from decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 108\u2013125. Springer, Heidelberg (2008)"},{"key":"35_CR14","doi-asserted-by":"crossref","unstructured":"Camenisch, J., Chandran, N., Shoup, V.: A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. Cryptology ePrint Archive, Report 2008\/375 (2008)","DOI":"10.1007\/978-3-642-01001-9_20"},{"key":"35_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/3-540-44987-6_7","volume-title":"Advances in Cryptology - EUROCRYPT 2001","author":"J. Camenisch","year":"2001","unstructured":"Camenisch, J., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol.\u00a02045, pp. 93\u2013118. Springer, Heidelberg (2001)"},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"Coppersmith, D.: Rapid multiplication of rectangular matrices. SICOMP: SIAM Journal on Computing\u00a011 (1982)","DOI":"10.1137\/0211037"},{"key":"35_CR17","unstructured":"Damg\u00e5rd, I.B., Nielsen, J.B.: An efficient pseudo-random generator with applications to public-key encryption and constant-round multiparty computation (unpublished) (2002)"},{"key":"35_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/3-540-36413-7_7","volume-title":"Security in Communication Networks","author":"N. Dedic","year":"2003","unstructured":"Dedic, N., Reyzin, L., Vadhan, S.P.: An improved pseudorandom generator based on hardness of factoring. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol.\u00a02576, pp. 88\u2013101. Springer, Heidelberg (2003)"},{"key":"35_CR19","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Kalai, Y.T., Lovett, S.: Cryptography with auxiliary inputs. In: Proc. 41st STOC (2009)","DOI":"10.1145\/1536414.1536498"},{"key":"35_CR20","doi-asserted-by":"crossref","unstructured":"Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. CACM: Communications of the ACM\u00a028 (1985)","DOI":"10.1145\/3812.3818"},{"key":"35_CR21","doi-asserted-by":"crossref","unstructured":"Feldman, V., Gopalan, P., Khot, S., Ponnuswami, A.K.: New results for learning noisy parities and halfspaces. In: FOCS, pp. 563\u2013574 (2006)","DOI":"10.1109\/FOCS.2006.51"},{"key":"35_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"35_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-540-30576-7_17","volume-title":"Theory of Cryptography","author":"M.J. Freedman","year":"2005","unstructured":"Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol.\u00a03378, pp. 303\u2013324. Springer, Heidelberg (2005)"},{"issue":"2","key":"35_CR24","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00145-004-0215-y","volume":"18","author":"R. Gennaro","year":"2005","unstructured":"Gennaro, R.: An improved pseudo-random generator based on the discrete logarithm problem. J. Cryptology\u00a018(2), 91\u2013110 (2005)","journal-title":"J. Cryptology"},{"key":"35_CR25","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"},{"key":"35_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/978-3-540-70583-3_55","volume-title":"Automata, Languages and Programming","author":"H. Gilbert","year":"2008","unstructured":"Gilbert, H., Robshaw, M.J.B., Seurin, Y.: How to encrypt with the LPN problem. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol.\u00a05126, pp. 679\u2013690. Springer, Heidelberg (2008)"},{"key":"35_CR27","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. of the ACM\u00a033, 792\u2013807 (1986)","journal-title":"J. of the ACM"},{"key":"35_CR28","doi-asserted-by":"crossref","unstructured":"Haitner, I., Holenstein, T.: On the (im)possibility of key dependent encryption. In: TCC, pp. 202\u2013219 (2009)","DOI":"10.1007\/978-3-642-00457-5_13"},{"key":"35_CR29","doi-asserted-by":"crossref","unstructured":"Halevi, S., Krawczyk, H.: Security under key-dependent inputs. In: CCS 2007, pp. 466\u2013475 (2007)","DOI":"10.1145\/1315245.1315303"},{"key":"35_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-540-78524-8_10","volume-title":"Theory of Cryptography","author":"C. Hazay","year":"2008","unstructured":"Hazay, C., Lindell, Y.: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In: Canetti, R. (ed.) TCC 2008. LNCS, vol.\u00a04948, pp. 155\u2013175. Springer, Heidelberg (2008)"},{"key":"35_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-78967-3_7","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"D. Hofheinz","year":"2008","unstructured":"Hofheinz, D., Unruh, D.: Towards key-dependent message security in the standard model. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol.\u00a04965, pp. 108\u2013126. Springer, Heidelberg (2008)"},{"key":"35_CR32","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":"35_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-540-45146-4_9","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"Y. Ishai","year":"2003","unstructured":"Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol.\u00a02729, pp. 145\u2013161. Springer, Heidelberg (2003)"},{"key":"35_CR34","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: Proc. 40th STOC (2008)","DOI":"10.1145\/1374376.1374438"},{"key":"35_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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.: Authenticating pervasive devices with human protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol.\u00a03621, pp. 293\u2013308. Springer, Heidelberg (2005)"},{"key":"35_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/11761679_6","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"J. Katz","year":"2006","unstructured":"Katz, J., Shin, J.S.: Parallel and concurrent security of the HB and HB $^{\\mbox{+}}$ protocols. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.\u00a04004, pp. 73\u201387. Springer, Heidelberg (2006)"},{"key":"35_CR37","doi-asserted-by":"crossref","unstructured":"Klivans, A.R., Sherstov, A.A.: Cryptographic hardness for learning intersections of halfspaces. In: FOCS, pp. 553\u2013562 (2006)","DOI":"10.1109\/FOCS.2006.24"},{"key":"35_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/3-540-44693-1_37","volume-title":"STACS 2001","author":"M. Krause","year":"2001","unstructured":"Krause, M., Lucks, S.: On the minimal hardware complexity of pseudorandom function generators (extended abstract). In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 419\u2013430. Springer, Heidelberg (2001)"},{"key":"35_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/3-540-44670-2_11","volume-title":"Cryptography and Lattices","author":"D. Micciancio","year":"2001","unstructured":"Micciancio, D.: Improving lattice based cryptosystems using the Hermite normal form. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol.\u00a02146, pp. 126\u2013145. Springer, Heidelberg (2001)"},{"issue":"1","key":"35_CR40","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); Preliminary version in FOCS 2004 (2004)","journal-title":"SIAM J. Comput."},{"key":"35_CR41","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, Heidelberg (2009)"},{"issue":"2","key":"35_CR42","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 Proc. 38th FOCS (1997)","journal-title":"J. ACM"},{"key":"35_CR43","doi-asserted-by":"crossref","unstructured":"Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: STOC (2009)","DOI":"10.1145\/1536414.1536461"},{"key":"35_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"35_CR45","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":"35_CR46","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84\u201393 (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"35_CR47","doi-asserted-by":"crossref","unstructured":"Spielman, D.A.: Linear-time encodable and decodable error-correcting codes. In: Proc. 27th STOC, pp. 388\u2013397 (1995)","DOI":"10.1145\/225058.225165"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology - CRYPTO 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03356-8_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T02:10:02Z","timestamp":1558491002000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03356-8_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642033551","9783642033568"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03356-8_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}