{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:51:03Z","timestamp":1781077863533,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585227","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1516-1526","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Lattice Problems beyond Polynomial Time"],"prefix":"10.1145","author":[{"given":"Divesh","family":"Aggarwal","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huck","family":"Bennett","sequence":"additional","affiliation":[{"name":"Oregon State University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zvika","family":"Brakerski","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Golovnev","sequence":"additional","affiliation":[{"name":"Georgetown University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajendra","family":"Kumar","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zeyong","family":"Li","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Spencer","family":"Peters","sequence":"additional","affiliation":[{"name":"Cornell University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noah","family":"Stephens-Davidowitz","sequence":"additional","affiliation":[{"name":"Cornell University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Divesh Aggarwal Huck Bennett Zvika Brakerski Alexander Golovnev Rajendra Kumar Zeyong Li Spencer Peters Noah Stephens-Davidowitz and Vinod Vaikuntanathan. 2022. Lattice Problems Beyond Polynomial Time. arxiv:2211.11693.  arxiv:2211.11693 \t\t\t\t  Divesh Aggarwal Huck Bennett Zvika Brakerski Alexander Golovnev Rajendra Kumar Zeyong Li Spencer Peters Noah Stephens-Davidowitz and Vinod Vaikuntanathan. 2022. Lattice Problems Beyond Polynomial Time. arxiv:2211.11693.  arxiv:2211.11693"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Divesh Aggarwal Huck Bennett Alexander Golovnev and Noah Stephens-Davidowitz. 2021. Fine-Grained Hardness of CVP(P)\u2014Everything That We Can Prove (and Nothing Else). In SODA. arxiv:1911.02440 \t\t\t\t  Divesh Aggarwal Huck Bennett Alexander Golovnev and Noah Stephens-Davidowitz. 2021. Fine-Grained Hardness of CVP(P)\u2014Everything That We Can Prove (and Nothing Else). In SODA. arxiv:1911.02440","DOI":"10.1137\/1.9781611976465.109"},{"key":"e_1_3_2_1_3_1","volume-title":"A Note on the Concrete Hardness of the Shortest Independent Vector in Lattices. Inform. Process. Lett., 167","author":"Aggarwal Divesh","year":"2021","unstructured":"Divesh Aggarwal and Eldon Chung . 2021. A Note on the Concrete Hardness of the Shortest Independent Vector in Lattices. Inform. Process. Lett., 167 ( 2021 ). Divesh Aggarwal and Eldon Chung. 2021. A Note on the Concrete Hardness of the Shortest Independent Vector in Lattices. Inform. Process. Lett., 167 (2021)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Divesh Aggarwal Zeyong Li and Noah Stephens-Davidowitz. 2021. A 2^n\/2-Time Algorithm for \u221a n-SVP and \u221a n-Hermite SVP and an Improved Time-Approximation Tradeoff for (H)SVP. In Eurocrypt. arxiv:2007.09556 \t\t\t\t  Divesh Aggarwal Zeyong Li and Noah Stephens-Davidowitz. 2021. A 2^n\/2-Time Algorithm for \u221a n-SVP and \u221a n-Hermite SVP and an Improved Time-Approximation Tradeoff for (H)SVP. In Eurocrypt. arxiv:2007.09556","DOI":"10.1007\/978-3-030-77870-5_17"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Divesh Aggarwal and Noah Stephens-Davidowitz. 2018. (Gap\/S)ETH Hardness of SVP. In STOC. arxiv:1712.00942 \t\t\t\t  Divesh Aggarwal and Noah Stephens-Davidowitz. 2018. (Gap\/S)ETH Hardness of SVP. In STOC. arxiv:1712.00942","DOI":"10.1145\/3188745.3188840"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai. 1996. Generating Hard Instances of Lattice Problems. In STOC. \t\t\t\t  Mikl\u00f3s Ajtai. 1996. Generating Hard Instances of Lattice Problems. In STOC.","DOI":"10.1145\/237814.237838"},{"key":"e_1_3_2_1_8_1","unstructured":"Mikl\u00f3s Ajtai. 1998. The Shortest Vector Problem in L_2 Is NP-hard for Randomized Reductions. In STOC. \t\t\t\t  Mikl\u00f3s Ajtai. 1998. The Shortest Vector Problem in L_2 Is NP-hard for Randomized Reductions. In STOC."},{"key":"e_1_3_2_1_9_1","unstructured":"Roberto Avanzi Joppe W. Bos L\u00e9o Ducas Eike Kiltz Tancr\u00e8de Lepoint Vadim Lyubashevsky John M. Schanck Peter Schwabe Gregor Seiler and Damien Stehl\u00e9. 2021. CRYSTALS-Kyber (Version 3.02) \u2013 Submission to Round 3 of the NIST Post-Quantum Project.  https:\/\/pq-crystals.org\/kyber\/resources.shtml \t\t\t\t  Roberto Avanzi Joppe W. Bos L\u00e9o Ducas Eike Kiltz Tancr\u00e8de Lepoint Vadim Lyubashevsky John M. Schanck Peter Schwabe Gregor Seiler and Damien Stehl\u00e9. 2021. CRYSTALS-Kyber (Version 3.02) \u2013 Submission to Round 3 of the NIST Post-Quantum Project.  https:\/\/pq-crystals.org\/kyber\/resources.shtml"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01445125"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Boaz Barak Fernando G.S.L. Brandao Aram W. Harrow Jonathan Kelner David Steurer and Yuan Zhou. 2012. Hypercontractivity Sum-of-Squares Proofs and Their Applications. In STOC. \t\t\t\t  Boaz Barak Fernando G.S.L. Brandao Aram W. Harrow Jonathan Kelner David Steurer and Yuan Zhou. 2012. Hypercontractivity Sum-of-Squares Proofs and Their Applications. In STOC.","DOI":"10.1145\/2213977.2214006"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Huck Bennett. 2022. The Complexity of the Shortest Vector Problem. Invited survey. To appear SIGACT News Open Problems Column. \t\t\t\t  Huck Bennett. 2022. The Complexity of the Shortest Vector Problem. Invited survey. To appear SIGACT News Open Problems Column.","DOI":"10.1145\/3586165.3586172"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Huck Bennett Alexander Golovnev and Noah Stephens-Davidowitz. 2017. On the Quantitative Hardness of CVP. In FOCS. arxiv:1704.03928 \t\t\t\t  Huck Bennett Alexander Golovnev and Noah Stephens-Davidowitz. 2017. On the Quantitative Hardness of CVP. In FOCS. arxiv:1704.03928","DOI":"10.1109\/FOCS.2017.11"},{"key":"e_1_3_2_1_14_1","unstructured":"Huck Bennett Chris Peikert and Yi Tang. 2022. Improved Hardness of BDD and SVP under Gap-(S)ETH. In ITCS. \t\t\t\t  Huck Bennett Chris Peikert and Yi Tang. 2022. Improved Hardness of BDD and SVP under Gap-(S)ETH. In ITCS."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Zvika Brakerski Adeline Langlois Chris Peikert Oded Regev and Damien Stehl\u00e9. 2013. Classical Hardness of Learning with Errors. In STOC. arxiv:1306.0281 \t\t\t\t  Zvika Brakerski Adeline Langlois Chris Peikert Oded Regev and Damien Stehl\u00e9. 2013. Classical Hardness of Learning with Errors. In STOC. arxiv:1306.0281","DOI":"10.1145\/2488608.2488680"},{"key":"e_1_3_2_1_16_1","unstructured":"Zvika Brakerski Noah Stephens-Davidowitz and Vinod Vaikuntanathan. 2021. On the Hardness of Average-Case k-SUM. In RANDOM. \t\t\t\t  Zvika Brakerski Noah Stephens-Davidowitz and Vinod Vaikuntanathan. 2021. On the Hardness of Average-Case k-SUM. In RANDOM."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1649"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0019-y"},{"key":"e_1_3_2_1_19_1","volume-title":"Nguyen","author":"Gama Nicolas","year":"2008","unstructured":"Nicolas Gama and Phong Q . Nguyen . 2008 . Finding Short Lattice Vectors within Mordell\u2019s Inequality. In STOC. Nicolas Gama and Phong Q. Nguyen. 2008. Finding Short Lattice Vectors within Mordell\u2019s Inequality. In STOC."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Craig Gentry Chris Peikert and Vinod Vaikuntanathan. 2008. Trapdoors for Hard Lattices and New Cryptographic Constructions. In STOC. https:\/\/eprint.iacr.org\/2007\/432 \t\t\t\t  Craig Gentry Chris Peikert and Vinod Vaikuntanathan. 2008. Trapdoors for Hard Lattices and New Cryptographic Constructions. In STOC. https:\/\/eprint.iacr.org\/2007\/432","DOI":"10.1145\/1374376.1374407"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1686"},{"key":"e_1_3_2_1_22_1","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"Goldreich Oded","year":"1996","unstructured":"Oded Goldreich , Shafi Goldwasser , and Shai Halevi . 2011. Collision-Free Hashing from Lattice Problems . In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation . Springer , 30\u201339. See also the original version https:\/\/eccc.weizmann.ac.il\/eccc-reports\/ 1996 \/TR96-042\/index.html Oded Goldreich, Shafi Goldwasser, and Shai Halevi. 2011. Collision-Free Hashing from Lattice Problems. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Springer, 30\u201339. See also the original version https:\/\/eccc.weizmann.ac.il\/eccc-reports\/1996\/TR96-042\/index.html"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00083-6"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a023"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089027"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Vadim Lyubashevsky and Daniele Micciancio. 2009. On Bounded Distance Decoding Unique Shortest Vectors and the Minimum Distance Problem. In CRYPTO. \t\t\t\t  Vadim Lyubashevsky and Daniele Micciancio. 2009. On Bounded Distance Decoding Unique Shortest Vectors and the Minimum Distance Problem. In CRYPTO.","DOI":"10.1007\/978-3-642-03356-8_34"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700373039"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a022"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Daniele Micciancio and Chris Peikert. 2013. Hardness of SIS and LWE with Small Parameters. In CRYPTO. \t\t\t\t  Daniele Micciancio and Chris Peikert. 2013. Hardness of SIS and LWE with Small Parameters. In CRYPTO.","DOI":"10.1007\/978-3-642-40041-4_2"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447360"},{"key":"e_1_3_2_1_32_1","unstructured":"NIST. 2022. Selected Algorithms 2022 - Post-Quantum Cryptography.  https:\/\/csrc.nist.gov\/Projects\/post-quantum-cryptography\/selected-algorithms-2022 \t\t\t\t  NIST. 2022. Selected Algorithms 2022 - Post-Quantum Cryptography.  https:\/\/csrc.nist.gov\/Projects\/post-quantum-cryptography\/selected-algorithms-2022"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Chris Peikert. 2009. Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem. In STOC. \t\t\t\t  Chris Peikert. 2009. Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem. In STOC.","DOI":"10.1145\/1536414.1536461"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000074"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Chris Peikert Oded Regev and Noah Stephens-Davidowitz. 2017. Pseudorandomness of Ring-LWE for Any Ring and Modulus. In STOC. \t\t\t\t  Chris Peikert Oded Regev and Noah Stephens-Davidowitz. 2017. Pseudorandomness of Ring-LWE for Any Ring and Modulus. In STOC.","DOI":"10.1145\/3055399.3055489"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2796561.2796598"},{"key":"e_1_3_2_1_38_1","volume-title":"Another NP-Complete Problem and the Complexity of Computing Short Vectors in a Lattice","author":"van Emde Boas Peter","unstructured":"Peter van Emde Boas . 1981. Another NP-Complete Problem and the Complexity of Computing Short Vectors in a Lattice . University of Amsterdam , Department of Mathematics, Netherlands. Peter van Emde Boas. 1981. Another NP-Complete Problem and the Complexity of Computing Short Vectors in a Lattice. University of Amsterdam, Department of Mathematics, Netherlands."},{"key":"e_1_3_2_1_39_1","unstructured":"Ryan Williams. 2016. Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. In CCC. \t\t\t\t  Ryan Williams. 2016. Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. In CCC."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585227","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:02Z","timestamp":1750178822000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":39,"alternative-id":["10.1145\/3564246.3585227","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585227","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}