{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T16:20:43Z","timestamp":1782404443512,"version":"3.54.5"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","award":["15848"],"award-info":[{"award-number":["15848"]}],"id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["DAAD19-03-1-0082"],"award-info":[{"award-number":["DAAD19-03-1-0082"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:p>\n            Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the \u201clearning from parity with error\u201d problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a\n            <jats:italic>quantum<\/jats:italic>\n            algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., nonquantum).\n          <\/jats:p>\n          <jats:p>\n            We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) and encrypting a message increases its size by a factor of \u00d5(\n            <jats:italic>n<\/jats:italic>\n            ) (in previous cryptosystems these values are \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            ) and \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ), respectively). In fact, under the assumption that all parties share a random bit string of length \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ), the size of the public key can be reduced to \u00d5(\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/1568318.1568324","type":"journal-article","created":{"date-parts":[[2009,9,8]],"date-time":"2009-09-08T12:53:03Z","timestamp":1252414383000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1761,"title":["On lattices, learning with errors, random linear codes, and cryptography"],"prefix":"10.1145","volume":"56","author":[{"given":"Oded","family":"Regev","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,9,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237838"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060604"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258604"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380857"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_28"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946338"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579403"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01445125"},{"key":"e_1_2_1_10_1","volume-title":"Lecture Notes in Computer Science","volume":"773","author":"Blum A.","unstructured":"Blum , A. , Furst , M. , Kearns , M. , and Lipton , R. J . 1994. Cryptographic primitives based on hard learning problems. In Advances in cryptology\u2014CRYPTO '93 . Lecture Notes in Computer Science , vol. 773 . Springer-Verlag, Berlin, Germany, 278--291. Blum, A., Furst, M., Kearns, M., and Lipton, R. J. 1994. Cryptographic primitives based on hard learning problems. In Advances in cryptology\u2014CRYPTO '93. Lecture Notes in Computer Science, vol. 773. Springer-Verlag, Berlin, Germany, 278--291."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792543"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Cai J.-Y.","unstructured":"Cai , J.-Y. , and Nerurkar , A . 1997. An improved worst-case to average-case connection for lattice problems . In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press , Los Alamitos, CA, 468--477. Cai, J.-Y., and Nerurkar, A. 1997. An improved worst-case to average-case connection for lattice problems. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 468--477."},{"key":"e_1_2_1_13_1","unstructured":"Cash D. Peikert C. and Sahai A. 2009. Efficient circular-secure encryption from hard learning problems. Submitted.  Cash D. Peikert C. and Sahai A. 2009. Efficient circular-secure encryption from hard learning problems. Submitted."},{"key":"e_1_2_1_14_1","volume-title":"revised ed. Advanced Lectures in Mathematics. Friedr. Vieweg&amp;Sohn","author":"Ebeling W.","unstructured":"Ebeling , W. 2002. Lattices and Codes , revised ed. Advanced Lectures in Mathematics. Friedr. Vieweg&amp;Sohn , Braunschweig, Germany . (A course partially based on lectures by F. Hirzebruch .) Ebeling, W. 2002. Lattices and Codes, revised ed. Advanced Lectures in Mathematics. Friedr. Vieweg&amp;Sohn, Braunschweig, Germany. (A course partially based on lectures by F. Hirzebruch.)"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374407"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00083-6"},{"key":"e_1_2_1_18_1","unstructured":"Grover L. and Rudolph T. 2002. Creating superpositions that correspond to efficiently integrable probability distributions. In quant-ph\/0208112 http:\/\/xxx.lanl.gov.  Grover L. and Rudolph T. 2002. Creating superpositions that correspond to efficiently integrable probability distributions. In quant-ph\/0208112 http:\/\/xxx.lanl.gov."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63486"},{"key":"e_1_2_1_20_1","unstructured":"Katz J. and Lindell Y. 2008. Introduction to modern cryptography. Chapman&amp;Hall\/CRC Cryptography and Network Security. Chapman&amp;Hall\/CRC Boca Raton FL.   Katz J. and Lindell Y. 2008. Introduction to modern cryptography. Chapman&amp;Hall\/CRC Cryptography and Network Security. Chapman&amp;Hall\/CRC Boca Raton FL."},{"key":"e_1_2_1_21_1","volume-title":"Lecture Notes in Comput. Sci.","volume":"4450","author":"Kawachi A.","unstructured":"Kawachi , A. , Tanaka , K. , and Xagawa , K . 2007. Multi-bit cryptosystems based on lattice problems. In Public Key Cryptography -- PKC 2007 . Lecture Notes in Comput. Sci. , vol. 4450 . Springer, Berlin, 315--329. Kawachi, A., Tanaka, K., and Xagawa, K. 2007. Multi-bit cryptosystems based on lattice problems. In Public Key Cryptography -- PKC 2007. Lecture Notes in Comput. Sci., vol. 4450. Springer, Berlin, 315--329."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.008"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Kumar R.","unstructured":"Kumar , R. , and Sivakumar , D . 2001. On polynomial approximation to the shortest lattice vector length . In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 126--127. Kumar, R., and Sivakumar, D. 2001. On polynomial approximation to the shortest lattice vector length. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 126--127."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_41"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Lyubashevsky V. and Micciancio D. 2009. On bounded distance decoding unique shortest vectors and the minimum distance problem. Manuscript.  Lyubashevsky V. and Micciancio D. 2009. On bounded distance decoding unique shortest vectors and the minimum distance problem. Manuscript.","DOI":"10.1007\/978-3-642-03356-8_34"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433511"},{"key":"e_1_2_1_28_1","volume-title":"Complexity of Lattice Problems: A Cryptographic Perspective. The Kluwer International Series in Engineering and Computer Science","volume":"671","author":"Micciancio D.","unstructured":"Micciancio , D. , and Goldwasser , S . 2002 . Complexity of Lattice Problems: A Cryptographic Perspective. The Kluwer International Series in Engineering and Computer Science , vol. 671 . Kluwer Academic Publishers, Boston, MA. Micciancio, D., and Goldwasser, S. 2002. Complexity of Lattice Problems: A Cryptographic Perspective. The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers, Boston, MA."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447360"},{"key":"e_1_2_1_30_1","unstructured":"Moore C. Russell A. and Vazirani U. 2007. A classical one-way function to confound quantum adversaries. In quant-ph\/0701115 http:\/\/xxx.lanl.gov.  Moore C. Russell A. and Vazirani U. 2007. A classical one-way function to confound quantum adversaries. In quant-ph\/0701115 http:\/\/xxx.lanl.gov."},{"key":"e_1_2_1_31_1","unstructured":"Nielsen M. A. and Chuang I. L. 2000. Quantum Computation and Quantum Information. Cambridge University Press Cambridge MA.   Nielsen M. A. and Chuang I. L. 2000. Quantum Computation and Quantum Information. Cambridge University Press Cambridge MA."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0251-3"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536461"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_31"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374406"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039490"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90064-8"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1568318.1568324","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1568318.1568324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:49Z","timestamp":1750253929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1568318.1568324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["10.1145\/1568318.1568324"],"URL":"https:\/\/doi.org\/10.1145\/1568318.1568324","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]},"assertion":[{"value":"2007-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}