{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T01:47:31Z","timestamp":1775612851214,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Integrated Project QAP"},{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]},{"name":"IST directorate","award":["15848"],"award-info":[{"award-number":["15848"]}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1054495"],"award-info":[{"award-number":["CCF-1054495"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0716786"],"award-info":[{"award-number":["CNS-0716786"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001320","name":"Wolfson Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001320","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>The \u201clearning with errors\u201d (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives).<\/jats:p>\n          <jats:p>\n            We resolve this question in the affirmative by introducing an algebraic variant of LWE called\n            <jats:italic>ring-LWE<\/jats:italic>\n            , and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.\n          <\/jats:p>","DOI":"10.1145\/2535925","type":"journal-article","created":{"date-parts":[[2013,12,4]],"date-time":"2013-12-04T14:04:47Z","timestamp":1386165887000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":497,"title":["On Ideal Lattices and Learning with Errors over Rings"],"prefix":"10.1145","volume":"60","author":[{"given":"Vadim","family":"Lyubashevsky","sequence":"first","affiliation":[{"name":"INRIA and \u00c9cole Normale Sup\u00e9rieure, Paris"}]},{"given":"Chris","family":"Peikert","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}]},{"given":"Oded","family":"Regev","sequence":"additional","affiliation":[{"name":"Courant Institute, New York University"}]}],"member":"320","published-online":{"date-parts":[[2013,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_28"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881420"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"Generating hard instances of lattice problems","volume":"13","author":"Ajtai Mikl\u00f3s","year":"2004","unstructured":"Mikl\u00f3s Ajtai . 2004 . Generating hard instances of lattice problems . Quad. Matemat. 13 , 1 -- 32 . Mikl\u00f3s Ajtai. 2004. Generating hard instances of lattice problems. Quad. Matemat. 13, 1--32.","journal-title":"Quad. Matemat."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380857"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_28"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01445125"},{"key":"e_1_2_1_8_1","volume-title":"Lipton","author":"Blum Avrim","year":"1993","unstructured":"Avrim Blum , Merrick L. Furst , Michael J. Kearns , and Richard J . Lipton . 1993 . Cryptographic primitives based on hard learning problems. In Proceedings of CRYPTO. 278--291. Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. 1993. Cryptographic primitives based on hard learning problems. In Proceedings of CRYPTO. 278--291."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13013-7_29"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.12"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090262"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488680"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_27"},{"key":"e_1_2_1_14_1","volume-title":"A Course in Computational Algebraic Number Theory","author":"Cohen Henri","unstructured":"Henri Cohen . 1993. A Course in Computational Algebraic Number Theory . Springer . Henri Cohen. 1993. A Course in Computational Algebraic Number Theory. Springer."},{"key":"e_1_2_1_15_1","unstructured":"Keith Conrad. 2009. The different ideal. http:\/\/www.math.uconn.edu\/~kconrad\/blurbs\/ (last accessed 12 Oct. 2009).  Keith Conrad. 2009. The different ideal. http:\/\/www.math.uconn.edu\/~kconrad\/blurbs\/ (last accessed 12 Oct. 2009)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of CRYPTO. 10--18","author":"ElGamal Taher","year":"1984","unstructured":"Taher ElGamal . 1984 . A public key cryptosystem and a signature scheme based on discrete logarithms . In Proceedings of CRYPTO. 10--18 . Taher ElGamal. 1984. A public key cryptosystem and a signature scheme based on discrete logarithms. In Proceedings of CRYPTO. 10--18."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08538-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374407"},{"key":"e_1_2_1_21_1","volume-title":"Foundations of Cryptography","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2004. Foundations of Cryptography . Vol. II , Cambridge University Press . Oded Goldreich. 2004. Foundations of Cryptography. Vol. II, Cambridge University Press."},{"key":"e_1_2_1_22_1","volume-title":"Electron. Colloq. Computat. Complex. 3, 42","author":"Goldreich Oded","year":"1996","unstructured":"Oded Goldreich , Shafi Goldwasser , and Shai Halevi . 1996 . Collision-free hashing from lattice problems . Electron. Colloq. Computat. Complex. 3, 42 . Oded Goldreich, Shafi Goldwasser, and Shai Halevi. 1996. Collision-free hashing from lattice problems. Electron. Colloq. Computat. Complex. 3, 42."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of ICS. 230--240","author":"Goldwasser Shafi","year":"2010","unstructured":"Shafi Goldwasser , Yael Tauman Kalai , Chris Peikert , and Vinod Vaikuntanathan . 2010 . Robustness of the learning with errors assumption . In Proceedings of ICS. 230--240 . Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. 2010. Robustness of the learning with errors assumption. In Proceedings of ICS. 230--240."},{"key":"e_1_2_1_24_1","volume-title":"Silverman","author":"Hoffstein Jeffrey","year":"1998","unstructured":"Jeffrey Hoffstein , Jill Pipher , and Joseph H . Silverman . 1998 . NTRU : A ring-based public key cryptosystem. In Proceedings of ANTS. 267--288. Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. 1998. NTRU: A ring-based public key cryptosystem. In Proceedings of ANTS. 267--288."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89255-7_23"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Adeline Langlois and Damien Stehl\u00e9. 2013. Worst-case to average-case reductions for module lattices. Submitted.  Adeline Langlois and Damien Stehl\u00e9. 2013. Worst-case to average-case reductions for module lattices. Submitted.","DOI":"10.1007\/s10623-014-9938-4"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1964621.1964651"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214086"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1793774.1793789"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10366-7_35"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_43"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_13"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1802614.1802619"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71039-4_4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_3"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0234-9"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_41"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447360"},{"key":"e_1_2_1_39_1","volume-title":"Post Quantum Cryptography","author":"Micciancio Daniele","unstructured":"Daniele Micciancio and Oded Regev . 2009. Lattice-based cryptography . In Post Quantum Cryptography , Springer , 147--191. Daniele Micciancio and Oded Regev. 2009. Lattice-based cryptography. In Post Quantum Cryptography, Springer, 147--191."},{"key":"e_1_2_1_40_1","volume-title":"Vadhan","author":"Micciancio Daniele","year":"2003","unstructured":"Daniele Micciancio and Salil P . Vadhan . 2003 . Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. In Proceedings of CRYPTO. 282--298. Daniele Micciancio and Salil P. Vadhan. 2003. Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. In Proceedings of CRYPTO. 282--298."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806739"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536461"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_8"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250860"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374406"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_31"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_2_1_48_1","volume-title":"On class field towers","author":"Roquette Peter","unstructured":"Peter Roquette . 1967. On class field towers . In Algebraic Number Theory, John William Scott Cassels and Albrecht Fr\u00f6hlich Eds., Academic Press , 231--249. Peter Roquette. 1967. On class field towers. In Algebraic Number Theory, John William Scott Cassels and Albrecht Fr\u00f6hlich Eds., Academic Press, 231--249."},{"key":"e_1_2_1_49_1","volume-title":"A Computational Introduction to Number Theory and Algebra","author":"Shoup Victor","unstructured":"Victor Shoup . 2009. A Computational Introduction to Number Theory and Algebra . Cambridge University Press . Victor Shoup. 2009. A Computational Introduction to Number Theory and Algebra. Cambridge University Press."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008684.2008690"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10366-7_36"},{"key":"e_1_2_1_52_1","unstructured":"William Stein. 2004. A brief introduction to classical and adelic algebraic number theory. http:\/\/modular.math.washington.edu\/papers\/ant\/ (last accessed 12 Oct. 2009).  William Stein. 2004. A brief introduction to classical and adelic algebraic number theory. http:\/\/modular.math.washington.edu\/papers\/ant\/ (last accessed 12 Oct. 2009)."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2535925","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2535925","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:06Z","timestamp":1750234206000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2535925"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":52,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2535925"],"URL":"https:\/\/doi.org\/10.1145\/2535925","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2012-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}