{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T12:40:08Z","timestamp":1748781608293,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662493861"},{"type":"electronic","value":"9783662493878"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49387-8_16","type":"book-chapter","created":{"date-parts":[[2016,2,17]],"date-time":"2016-02-17T19:25:41Z","timestamp":1455737141000},"page":"417-446","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Public Key Encryption from Noisy Codewords"],"prefix":"10.1007","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[]},{"given":"Iddo","family":"Ben-Tov","sequence":"additional","affiliation":[]},{"given":"Ivan","family":"Damg\u00e5rd","sequence":"additional","affiliation":[]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[]},{"given":"Noga","family":"Ron-Zewi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,2,18]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC), pp. 99\u2013108. ACM Press (1996)","key":"16_CR1","DOI":"10.1145\/237814.237838"},{"doi-asserted-by":"crossref","unstructured":"Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case\/average-case equivalence. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing (STOC), pp. 284\u2013293. ACM Press (1997)","key":"16_CR2","DOI":"10.1145\/258533.258604"},{"issue":"4","key":"16_CR3","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1007\/s00037-011-0029-x","volume":"20","author":"M Alekhnovich","year":"2011","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. Comput. Complex. 20(4), 755\u2013786 (2011). Preliminary version in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003)","journal-title":"Comput. Complex."},{"key":"16_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. 5677, pp. 595\u2013618. Springer, Heidelberg (2009)"},{"issue":"4","key":"16_CR5","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s00145-009-9039-0","volume":"22","author":"B Applebaum","year":"2009","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography with constant input locality. J. Cryptology 22(4), 429\u2013469 (2009)","journal-title":"J. Cryptology"},{"doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Ben-Tov, I., Damg\u00e5rd, I., Ishai, Y., Ron-Zewi, N.: On public key encryption from noisy codewords. IACR Cryptology ePrint Archive, 2015:572 (2015)","key":"16_CR6","DOI":"10.1007\/978-3-662-49387-8_16"},{"doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Lovett, S., Ron-Zewi, N.: An additive combinatorics approach relating rank to communication complexity. J. ACM (2013) (to appear)","key":"16_CR7","DOI":"10.1109\/FOCS.2012.39"},{"doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Zewi, N.: From affine to two-source extractors via approximate duality. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pp. 177\u2013186. ACM Press (2011)","key":"16_CR8","DOI":"10.1145\/1993636.1993661"},{"doi-asserted-by":"crossref","unstructured":"Bhowmick, A., Dvir, Z., Lovett, S.: New bounds for matching vector families. In: Proceedings of the 47th ACM Symposium on Theory of Computing (STOC), pp. 823\u2013832. ACM Press (2013)","key":"16_CR9","DOI":"10.1145\/2488608.2488713"},{"key":"16_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., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278\u2013291. Springer, Heidelberg (1994)"},{"issue":"4","key":"16_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, the statistical query model. J. ACM 50(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"unstructured":"Damg\u00e5rd, I., Park, S.: Is public-key encryption based on LPN practical? IACR Cryptology ePrint Archive, 2011:699 (2012)","key":"16_CR12"},{"issue":"6","key":"16_CR13","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 Trans. Inf. Theory 22(6), 644\u2013654 (1976)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"16_CR14","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1137\/100804322","volume":"40","author":"Z Dvir","year":"2011","unstructured":"Dvir, Z., Gopalan, P., Yekhanin, S.: Matching vector codes. SIAM J. Comput. 40(4), 1154\u20131178 (2011). Preliminary version in Proceedings of the IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS 2011)","journal-title":"SIAM J. Comput."},{"key":"16_CR15","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. 3027, pp. 342\u2013360. Springer, Heidelberg (2004)"},{"issue":"6","key":"16_CR16","doi-asserted-by":"publisher","first-page":"1694","DOI":"10.1137\/090772721","volume":"41","author":"K Efremenko","year":"2012","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. SIAM J. Comput. 41(6), 1694\u20131703 (2012). Preliminary version in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"16_CR17","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T ElGamal","year":"1985","unstructured":"ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469\u2013472 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC). ACM Press (2008)","key":"16_CR18","DOI":"10.1145\/1374376.1374407"},{"key":"16_CR19","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/BFb0052231","volume-title":"Advances in Cryptology \u2014 CRYPTO '97","author":"Oded Goldreich","year":"1997","unstructured":"Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112\u2013131. Springer, Heidelberg (1997)"},{"doi-asserted-by":"crossref","unstructured":"Green, B.: Finite field models in additive combinatorics. In London Mathematical Society Lecture Note Series, vol. 324. Cambridge University Press, Cambridge (2005)","key":"16_CR20","DOI":"10.1017\/CBO9780511734885.002"},{"key":"16_CR21","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s004930070032","volume":"20","author":"V Grolmusz","year":"2000","unstructured":"Grolmusz, V.: Superpolynomial size set-systems with restricted intersections mod 6 and explicit ramsey graphs. Combinatorica 20, 71\u201386 (2000)","journal-title":"Combinatorica"},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BFb0054868","volume-title":"Algorithmic Number Theory","author":"J Hoffstein","year":"1998","unstructured":"Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267\u2013288. Springer, Heidelberg (1998)"},{"key":"16_CR23","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":"NJ Hopper","year":"2001","unstructured":"Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52\u201366. Springer, Heidelberg (2001)"},{"doi-asserted-by":"crossref","unstructured":"Kalai, A.T., Mansour, Y., Verbin, E.: On agnostic boosting and parity learning. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 629\u2013638. ACM Press (2008)","key":"16_CR24","DOI":"10.1145\/1374376.1374466"},{"issue":"3","key":"16_CR25","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1137\/100811945","volume":"42","author":"S Kopparty","year":"2013","unstructured":"Kopparty, S., Saraf, S.: Local list-decoding and testing of random linear codes from high error. SIAM J. Comput. 42(3), 1302\u20131326 (2013)","journal-title":"SIAM J. Comput."},{"key":"16_CR26","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. 6558, pp. 319\u2013339. Springer, Heidelberg (2011)"},{"unstructured":"Lovett, S.: Additive combinatorics and its applications in theoretical computer science (2013)","key":"16_CR27"},{"doi-asserted-by":"crossref","unstructured":"Lovett, S.: Communication is bounded by root of rank. In: Proceedings of the 46th ACM Symposium on Theory of Computing (STOC). ACM Press (2014)","key":"16_CR28","DOI":"10.1145\/2591796.2591799"},{"key":"16_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/11538462_32","volume-title":"Approximation, Randomization and Combinatorial Optimization","author":"V Lyubashevsky","year":"2005","unstructured":"Lyubashevsky, V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol. 3624, pp. 378\u2013389. Springer, Heidelberg (2005)"},{"issue":"6","key":"16_CR30","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/2535925","volume":"60","author":"V Lyubashevsky","year":"2013","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. J. ACM 60(6), 43 (2013)","journal-title":"J. ACM"},{"unstructured":"McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. JPL DSN Progress Report (1978)","key":"16_CR31"},{"key":"16_CR32","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. 2146, pp. 126\u2013145. Springer, Heidelberg (2001)"},{"doi-asserted-by":"crossref","unstructured":"Micciancio, D.: Duality in lattice-based cryptography. In Public Key Cryptography (invited talk) (2010)","key":"16_CR33","DOI":"10.1007\/978-1-4419-5906-5_417"},{"key":"16_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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. 6841, pp. 465\u2013484. Springer, Heidelberg (2011)"},{"doi-asserted-by":"crossref","unstructured":"Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 147\u2013192. Springer, Heidelberg (2009)","key":"16_CR35","DOI":"10.1007\/978-3-540-88702-7_5"},{"key":"16_CR36","first-page":"159","volume":"15","author":"H Niederreiter","year":"1986","unstructured":"Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Prob. Control Inf. Theory (Problemy Upravlenija i Teorii Informacii) 15, 159\u2013166 (1986)","journal-title":"Prob. Control Inf. Theory (Problemy Upravlenija i Teorii Informacii)"},{"key":"16_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-642-27660-6_9","volume-title":"SOFSEM 2012: Theory and Practice of Computer Science","author":"K Pietrzak","year":"2012","unstructured":"Pietrzak, K.: Cryptography from learning parity with noise. In: Bielikov\u00e1, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur\u00e1n, G. (eds.) SOFSEM 2012. LNCS, vol. 7147, pp. 99\u2013114. Springer, Heidelberg (2012)"},{"unstructured":"Rabin, M.: Digitalized signatures and public-key functions as intractable as factorization. MIT LCS TR-212 (1979)","key":"16_CR38"},{"issue":"6","key":"16_CR39","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1145\/1039488.1039490","volume":"51","author":"O Regev","year":"2004","unstructured":"Regev, O.: New lattice-based cryptographic constructions. J. ACM 51(6), 899\u2013942 (2004)","journal-title":"J. ACM"},{"issue":"6","key":"16_CR40","doi-asserted-by":"publisher","first-page":"34: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 56(6), 34:1\u201334:40 (2009). Preliminary version in Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Regev, O.: The learning with errors problem (invited survey). In: IEEE Conference on Computational Complexity, pp. 191\u2013204 (2010)","key":"16_CR41","DOI":"10.1109\/CCC.2010.26"},{"issue":"1","key":"16_CR42","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/357980.358017","volume":"26","author":"RL Rivest","year":"1983","unstructured":"Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems (reprint). Commun. ACM 26(1), 96\u201399 (1983)","journal-title":"Commun. ACM"},{"doi-asserted-by":"crossref","unstructured":"Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Proceedings of the 46th Annual ACM Symposium on the Theory of Computing (STOC), pp. 475\u2013484. ACM Press (2014)","key":"16_CR43","DOI":"10.1145\/2591796.2591825"},{"key":"16_CR44","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. 5912, pp. 617\u2013635. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Public-Key Cryptography \u2013 PKC 2016"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49387-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T12:12:30Z","timestamp":1748779950000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49387-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662493861","9783662493878"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49387-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"18 February 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}