{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:51:08Z","timestamp":1781077868166,"version":"3.54.1"},"reference-count":93,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T00:00:00Z","timestamp":1677542400000},"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":["SIGACT News"],"published-print":{"date-parts":[[2023,2,28]]},"abstract":"<jats:p>Computational problems on point lattices play a central role in many areas of computer science including integer programming, coding theory, cryptanalysis, and especially the design of secure cryptosystems. In this survey, we present known results and open questions related to the complexity of the most important of these problems, the Shortest Vector Problem (SVP).<\/jats:p>","DOI":"10.1145\/3586165.3586172","type":"journal-article","created":{"date-parts":[[2023,3,1]],"date-time":"2023-03-01T23:07:16Z","timestamp":1677712036000},"page":"37-61","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["The Complexity of the Shortest Vector Problem"],"prefix":"10.1145","volume":"54","author":[{"given":"Huck","family":"Bennett","sequence":"first","affiliation":[{"name":"Oregon State University, OR, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Lattice problems beyond polynomial time","author":"Aggarwal D.","year":"2022","unstructured":"[ABB+22] D. Aggarwal , H. Bennett , Z. Brakerski , A. Golovnev , R. Kumar , Z. Li , S. Peters , N. Stephens- Davidowitz , and V. Vaikuntanathan . Lattice problems beyond polynomial time , 2022 . Preprint . 4, 13, 14, 18 [ABB+22] D. Aggarwal, H. Bennett, Z. Brakerski, A. Golovnev, R. Kumar, Z. Li, S. Peters, N. Stephens- Davidowitz, and V. Vaikuntanathan. Lattice problems beyond polynomial time, 2022. Preprint. 4, 13, 14, 18"},{"key":"e_1_2_1_2_1","volume-title":"Cryptographic suite for algebraic lattices (CRYSTALS). https: \/\/pq-crystals.org\/","author":"Avanzi R.","year":"2017","unstructured":"[ABD+17] R. Avanzi , J. Bos , L. Ducas , E. Kiltz , T. Lepoint , V. Lyubashevsky , J. M. Schanck , P. Schwabe , G. Seiler , and D. Stehl\u00b4e . Cryptographic suite for algebraic lattices (CRYSTALS). https: \/\/pq-crystals.org\/ , 2017 . 1, 16 [ABD+17] R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler, and D. Stehl\u00b4e. Cryptographic suite for algebraic lattices (CRYSTALS). https: \/\/pq-crystals.org\/, 2017. 1, 16"},{"key":"e_1_2_1_3_1","first-page":"6","article-title":"Fine-grained hardness of CVP(P)-everything that we can prove (and nothing else)","author":"Aggarwal D.","year":"2021","unstructured":"[ABGS21] D. Aggarwal , H. Bennett , A. Golovnev , and N. Stephens-Davidowitz . Fine-grained hardness of CVP(P)-everything that we can prove (and nothing else) . In SODA. 2021 . 6 , 7 [ABGS21] D. Aggarwal, H. Bennett, A. Golovnev, and N. Stephens-Davidowitz. Fine-grained hardness of CVP(P)-everything that we can prove (and nothing else). In SODA. 2021. 6, 7","journal-title":"SODA."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"e_1_2_1_5_1","volume-title":"NTRU} schemes! In SCN.","author":"Albrecht M. R.","year":"2018","unstructured":"[ACD+18] M. R. Albrecht , B. R. Curtis , A. Deo , A. Davidson , R. Player , E. W. Postlethwaite , F. Virdia , and T. Wunderer . Estimate all the {LWE , NTRU} schemes! In SCN. 2018 . 5 [ACD+18] M. R. Albrecht, B. R. Curtis, A. Deo, A. Davidson, R. Player, E. W. Postlethwaite, F. Virdia, and T. Wunderer. Estimate all the {LWE, NTRU} schemes! In SCN. 2018. 5"},{"key":"e_1_2_1_6_1","volume-title":"STACS.","author":"Aggarwal D.","year":"2021","unstructured":"[ACKS21] D. Aggarwal , Y. Chen , R. Kumar , and Y. Shen . Improved (provable) algorithms for the Shortest Vector Problem via bounded distance decoding . In STACS. 2021 . 6 [ACKS21] D. Aggarwal, Y. Chen, R. Kumar, and Y. Shen. Improved (provable) algorithms for the Shortest Vector Problem via bounded distance decoding. In STACS. 2021. 6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.05.003"},{"key":"e_1_2_1_8_1","volume-title":"ASIACRYPT.","author":"Albrecht M. R.","year":"2017","unstructured":"[AD17] M. R. Albrecht and A. Deo . Large modulus Ring-LWE ? Module-LWE . In ASIACRYPT. 2017 . 17 [AD17] M. R. Albrecht and A. Deo. Large modulus Ring-LWE ? Module-LWE. In ASIACRYPT. 2017. 17"},{"key":"e_1_2_1_9_1","first-page":"5","article-title":"Post-quantum key exchange - A new hope","author":"Alkim E.","year":"2016","unstructured":"[ADPS16] E. Alkim , L. Ducas , T. P\u00a8oppelmann , and P. Schwabe . Post-quantum key exchange - A new hope . In USENIX. 2016 . 5 , 6 [ADPS16] E. Alkim, L. Ducas, T. P\u00a8oppelmann, and P. Schwabe. Post-quantum key exchange - A new hope. In USENIX. 2016. 5, 6","journal-title":"USENIX."},{"key":"e_1_2_1_10_1","volume-title":"STOC.","author":"Aggarwal D.","year":"2015","unstructured":"[ADRS15] D. Aggarwal , D. Dadush , O. Regev , and N. Stephens-Davidowitz . Solving the Shortest Vector Problem in 2n time using discrete Gaussian sampling: Extended abstract . In STOC. 2015 . 5 [ADRS15] D. Aggarwal, D. Dadush, O. Regev, and N. Stephens-Davidowitz. Solving the Shortest Vector Problem in 2n time using discrete Gaussian sampling: Extended abstract. In STOC. 2015. 5"},{"key":"e_1_2_1_11_1","volume-title":"STOC.","author":"Ajtai M.","year":"1996","unstructured":"[Ajt96] M. Ajtai . Generating hard instances of lattice problems (extended abstract) . In STOC. 1996 . 12 [Ajt96] M. Ajtai. Generating hard instances of lattice problems (extended abstract). In STOC. 1996. 12"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276705"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","DOI":"10.1109\/TIT.2014.2340869","article-title":"A simple deterministic reduction for the gap minimum distance of code problem","author":"Austrin P.","year":"2014","unstructured":"[AK11] P. Austrin and S. Khot . A simple deterministic reduction for the gap minimum distance of code problem . IEEE Trans. Inf. Theory , 2014 . Preliminary verison in ICALP 2011. 10 [AK11] P. Austrin and S. Khot. A simple deterministic reduction for the gap minimum distance of code problem. IEEE Trans. Inf. Theory, 2014. Preliminary verison in ICALP 2011. 10","journal-title":"IEEE Trans. Inf. Theory"},{"key":"e_1_2_1_14_1","volume-title":"Why we couldn't prove SETH hardness of CVP for even norms!","author":"Aggarwal D.","year":"2022","unstructured":"[AK22] D. Aggarwal and R. Kumar . Why we couldn't prove SETH hardness of CVP for even norms! , 2022 . Available at https:\/\/arxiv.org\/abs\/2211.04385. 6, 7 [AK22] D. Aggarwal and R. Kumar. Why we couldn't prove SETH hardness of CVP for even norms!, 2022. Available at https:\/\/arxiv.org\/abs\/2211.04385. 6, 7"},{"key":"e_1_2_1_15_1","volume-title":"CRYPTO.","author":"Aggarwal D.","year":"2020","unstructured":"[ALNS20] D. Aggarwal , J. Li , P. Q. Nguyen , and N. Stephens-Davidowitz . Slide reduction, revisited-filling the gaps in SVP approximation . In CRYPTO. 2020 . 14 [ALNS20] D. Aggarwal, J. Li, P. Q. Nguyen, and N. Stephens-Davidowitz. Slide reduction, revisited-filling the gaps in SVP approximation. In CRYPTO. 2020. 14"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"e_1_2_1_17_1","first-page":"6","article-title":"(Gap\/S)ETH hardness of SVP","author":"Aggarwal D.","year":"2018","unstructured":"[AS18] D. Aggarwal and N. Stephens-Davidowitz . (Gap\/S)ETH hardness of SVP . In STOC. 2018 . 6 , 7, 11, 14 [AS18] D. Aggarwal and N. Stephens-Davidowitz. (Gap\/S)ETH hardness of SVP. In STOC. 2018. 6, 7, 11, 14","journal-title":"STOC."},{"issue":"3","key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/3444942","article-title":"Parameterized intractability of even set and shortest vector problem","volume":"68","author":"Bhattacharyya A.","year":"2021","unstructured":"[BBE+21] A. Bhattacharyya , E. Bonnet , L. Egri , S. Ghoshal , K. C. S., B. Lin , P. Manurangsi , and D. Marx . Parameterized intractability of even set and shortest vector problem . J. ACM , 68 ( 3 ), 2021 . 15 , 16 [BBE+21] A. Bhattacharyya, E. Bonnet, L. Egri, S. Ghoshal, K. C. S., B. Lin, P. Manurangsi, and D. Marx. Parameterized intractability of even set and shortest vector problem. J. ACM, 68(3), 2021. 15, 16","journal-title":"J. ACM"},{"key":"e_1_2_1_19_1","volume-title":"Parameterized inapproximability of the Minimum Distance Problem over all fields and the Shortest Vector Problem in all ?p norms","author":"Bennett H.","year":"2022","unstructured":"[BCGR22] H. Bennett , M. Cheraghchi , V. Guruswami , and J. Ribeiro . Parameterized inapproximability of the Minimum Distance Problem over all fields and the Shortest Vector Problem in all ?p norms , 2022 . Preprint . 16 [BCGR22] H. Bennett, M. Cheraghchi, V. Guruswami, and J. Ribeiro. Parameterized inapproximability of the Minimum Distance Problem over all fields and the Shortest Vector Problem in all ?p norms, 2022. Preprint. 16"},{"key":"e_1_2_1_20_1","volume-title":"SODA.","author":"Becker A.","year":"2016","unstructured":"[BDGL16] A. Becker , L. Ducas , N. Gama , and T. Laarhoven . New directions in nearest neighbor searching with applications to lattice sieving . In SODA. 2016 . 5 [BDGL16] A. Becker, L. Ducas, N. Gama, and T. Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In SODA. 2016. 5"},{"key":"e_1_2_1_21_1","volume-title":"Just how hard are rotations of Zn? Algorithms and cryptography with the simplest lattice. IACR Cryptol. ePrint Arch., page 1548","author":"Bennett H.","year":"2021","unstructured":"[BGPS21] H. Bennett , A. Ganju , P. Peetathawatchai , and N. Stephens-Davidowitz . Just how hard are rotations of Zn? Algorithms and cryptography with the simplest lattice. IACR Cryptol. ePrint Arch., page 1548 , 2021 . 15\\ [BGPS21] H. Bennett, A. Ganju, P. Peetathawatchai, and N. Stephens-Davidowitz. Just how hard are rotations of Zn? Algorithms and cryptography with the simplest lattice. IACR Cryptol. ePrint Arch., page 1548, 2021. 15\\"},{"key":"e_1_2_1_22_1","volume-title":"FOCS.","author":"Bennett H.","year":"2017","unstructured":"[BGS17] H. Bennett , A. Golovnev , and N. Stephens-Davidowitz . On the quantitative hardness of CVP . In FOCS. 2017 . 6 [BGS17] H. Bennett, A. Golovnev, and N. Stephens-Davidowitz. On the quantitative hardness of CVP. In FOCS. 2017. 6"},{"key":"e_1_2_1_23_1","volume-title":"Fine-grained hardness of lattice problems: Open questions","author":"Bennett H.","year":"2020","unstructured":"[BGS20] H. Bennett , A. Golovnev , and N. Stephens-Davidowitz . Fine-grained hardness of lattice problems: Open questions , 2020 . Available at https:\/\/blog.simons.berkeley.edu\/2020\/05\/ fine-grained-hardness-of-lattice-problems-open-questions\/. 1, 5, 6, 7 [BGS20] H. Bennett, A. Golovnev, and N. Stephens-Davidowitz. Fine-grained hardness of lattice problems: Open questions, 2020. Available at https:\/\/blog.simons.berkeley.edu\/2020\/05\/ fine-grained-hardness-of-lattice-problems-open-questions\/. 1, 5, 6, 7"},{"key":"e_1_2_1_24_1","volume-title":"STOC.","author":"Brakerski Z.","year":"2013","unstructured":"[BLP+13] Z. Brakerski , A. Langlois , C. Peikert , O. Regev , and D. Stehl\u00b4e . Classical hardness of learning with errors . In STOC. 2013 . 12 [BLP+13] Z. Brakerski, A. Langlois, C. Peikert, O. Regev, and D. Stehl\u00b4e. Classical hardness of learning with errors. In STOC. 2013. 12"},{"issue":"2","key":"e_1_2_1_25_1","first-page":"203","article-title":"Twenty years of attacks on the RSA cryptosystem","volume":"46","author":"Boneh D.","year":"1999","unstructured":"[Bon99] D. Boneh . Twenty years of attacks on the RSA cryptosystem . Not. of the Am. Math. Soc. , 46 ( 2 ): 203 -- 213 , 1999 . 1 [Bon99] D. Boneh. Twenty years of attacks on the RSA cryptosystem. Not. of the Am. Math. Soc., 46(2):203--213, 1999. 1","journal-title":"Not. of the Am. Math. Soc."},{"key":"e_1_2_1_26_1","volume-title":"CCC.","author":"Bennett H.","year":"2020","unstructured":"[BP20] H. Bennett and C. Peikert . Hardness of bounded distance decoding on lattices in ?p norms . In CCC. 2020 . 11 [BP20] H. Bennett and C. Peikert. Hardness of bounded distance decoding on lattices in ?p norms. In CCC. 2020. 11"},{"key":"e_1_2_1_27_1","volume-title":"Hardness of the (approximate) Shortest Vector Problem: A simple proof via Reed-Solomon codes. CoRR, abs\/2202.07736","author":"Bennett H.","year":"2022","unstructured":"[BP22] H. Bennett and C. Peikert . Hardness of the (approximate) Shortest Vector Problem: A simple proof via Reed-Solomon codes. CoRR, abs\/2202.07736 , 2022 . 10, 11, 12 [BP22] H. Bennett and C. Peikert. Hardness of the (approximate) Shortest Vector Problem: A simple proof via Reed-Solomon codes. CoRR, abs\/2202.07736, 2022. 10, 11, 12"},{"key":"e_1_2_1_28_1","volume-title":"A framework of quantum strong exponential-time hypotheses","author":"Buhrman H.","year":"2021","unstructured":"[BPS21] H. Buhrman , S. Patro , and F. Speelman . A framework of quantum strong exponential-time hypotheses . In M. Bl\u00a8aser and B. Monmege, editors, STACS. 2021 . 7 [BPS21] H. Buhrman, S. Patro, and F. Speelman. A framework of quantum strong exponential-time hypotheses. In M. Bl\u00a8aser and B. Monmege, editors, STACS. 2021. 7"},{"key":"e_1_2_1_29_1","first-page":"7","article-title":"Improved hardness of BDD and SVP under Gap-(S)ETH","author":"Bennett H.","year":"2022","unstructured":"[BPT22] H. Bennett , C. Peikert , and Y. Tang . Improved hardness of BDD and SVP under Gap-(S)ETH . In ITCS. 2022 . 7 , 11 [BPT22] H. Bennett, C. Peikert, and Y. Tang. Improved hardness of BDD and SVP under Gap-(S)ETH. In ITCS. 2022. 7, 11","journal-title":"ITCS."},{"key":"e_1_2_1_30_1","volume-title":"EUROCRYPT.","author":"Cramer R.","year":"2016","unstructured":"[CDPR16] R. Cramer , L. Ducas , C. Peikert , and O. Regev . Recovering short generators of principal ideals in cyclotomic rings . In EUROCRYPT. 2016 . 17 [CDPR16] R. Cramer, L. Ducas, C. Peikert, and O. Regev. Recovering short generators of principal ideals in cyclotomic rings. In EUROCRYPT. 2016. 17"},{"key":"e_1_2_1_31_1","volume-title":"EUROCRYPT.","author":"Cramer R.","year":"2017","unstructured":"[CDW17] R. Cramer , L. Ducas , and B. Wesolowski . Short Stickelberger class relations and application to Ideal-SVP . In EUROCRYPT. 2017 . 17 [CDW17] R. Cramer, L. Ducas, and B. Wesolowski. Short Stickelberger class relations and application to Ideal-SVP. In EUROCRYPT. 2017. 17"},{"key":"e_1_2_1_32_1","volume-title":"ETSI\/IQC 2nd Quantum-Safe Crypto Workshop","author":"Campbell P.","year":"2014","unstructured":"[CGS14] P. Campbell , M. Groves , and D. Shepherd . Soliloquy: A cautionary tale . ETSI\/IQC 2nd Quantum-Safe Crypto Workshop , 2014 . 17 [CGS14] P. Campbell, M. Groves, and D. Shepherd. Soliloquy: A cautionary tale. ETSI\/IQC 2nd Quantum-Safe Crypto Workshop, 2014. 17"},{"key":"e_1_2_1_33_1","volume-title":"Paper 2013\/052","author":"Cheng K.","year":"2013","unstructured":"[Che13] K. Cheng . Some complexity results and bit unpredictable for short vector problem. Cryptology ePrint Archive , Paper 2013\/052 , 2013 . https:\/\/eprint.iacr.org\/2013\/052. 15 [Che13] K. Cheng. Some complexity results and bit unpredictable for short vector problem. Cryptology ePrint Archive, Paper 2013\/052, 2013. https:\/\/eprint.iacr.org\/2013\/052. 15"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1649"},{"key":"e_1_2_1_35_1","volume-title":"International Conference.","author":"Coppersmith D.","year":"2001","unstructured":"[Cop01] D. Coppersmith . Finding small solutions to small degree polynomials. In Cryptography and Lattices , International Conference. 2001 . 1 [Cop01] D. Coppersmith. Finding small solutions to small degree polynomials. In Cryptography and Lattices, International Conference. 2001. 1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-6568-7","volume-title":"Sphere packings, lattices, and groups","author":"Conway J.","year":"1999","unstructured":"[CS99] J. Conway and N. J. A. Sloane . Sphere packings, lattices, and groups . Springer , 1999 . 1 [CS99] J. Conway and N. J. A. Sloane. Sphere packings, lattices, and groups. Springer, 1999. 1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2209198"},{"key":"e_1_2_1_38_1","volume-title":"Lattice Algorithms, and Deterministic","author":"Dadush D.","unstructured":"[Dad12] D. Dadush . Integer Programming , Lattice Algorithms, and Deterministic Volume Estimation. Ph.D. thesis, Georgia Institute of Technology, 2012 . 1 [Dad12] D. Dadush. Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation. Ph.D. thesis, Georgia Institute of Technology, 2012. 1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2568438"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00290-0"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.806118"},{"key":"e_1_2_1_43_1","volume-title":"CRYPTO.","author":"Ducas L.","year":"2019","unstructured":"[DPW19] L. Ducas , M. Plan\u00b8con , and B. Wesolowski . On the shortness of vectors to be found by the Ideal-SVP quantum algorithm . In CRYPTO. 2019 . 17 [DPW19] L. Ducas, M. Plan\u00b8con, and B. Wesolowski. On the shortness of vectors to be found by the Ideal-SVP quantum algorithm. In CRYPTO. 2019. 17"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1686"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00083-6"},{"key":"e_1_2_1_46_1","first-page":"4","article-title":"Finding short lattice vectors within Mordell's inequality","author":"Gama N.","year":"2008","unstructured":"[GN08] N. Gama and P. Q. Nguyen . Finding short lattice vectors within Mordell's inequality . In STOC. 2008 . 4 , 14 [GN08] N. Gama and P. Q. Nguyen. Finding short lattice vectors within Mordell's inequality. In STOC. 2008. 4, 14","journal-title":"STOC."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.878164"},{"key":"e_1_2_1_48_1","volume-title":"International Workshop on Information Security Applications.","author":"Hu G.","year":"2013","unstructured":"[HP13] G. Hu and Y. Pan . Improvements on reductions among different variants of SVP and CVP . In International Workshop on Information Security Applications. 2013 . 15 [HP13] G. Hu and Y. Pan. Improvements on reductions among different variants of SVP and CVP. In International Workshop on Information Security Applications. 2013. 15"},{"key":"e_1_2_1_49_1","volume-title":"ANTS.","author":"Hoffstein J.","year":"1998","unstructured":"[HPS98] J. Hoffstein , J. Pipher , and J. H. Silverman . NTRU: A ring-based public key cryptosystem . In ANTS. 1998 . 16 [HPS98] J. Hoffstein, J. Pipher, and J. H. Silverman. NTRU: A ring-based public key cryptosystem. In ANTS. 1998. 16"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a023"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2875343.2875346"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.07.002"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089027"},{"key":"e_1_2_1_54_1","volume-title":"On the unique shortest lattice vector problem. Theor. Comput. Sci., 255(1--2):641--648","author":"Kumar R.","year":"2001","unstructured":"[KS01] R. Kumar and D. Sivakumar . On the unique shortest lattice vector problem. Theor. Comput. Sci., 255(1--2):641--648 , 2001 . 15 [KS01] R. Kumar and D. Sivakumar. On the unique shortest lattice vector problem. Theor. Comput. Sci., 255(1--2):641--648, 2001. 15"},{"key":"e_1_2_1_55_1","volume-title":"CRYPTO.","author":"Laarhoven T.","year":"2015","unstructured":"[Laa15] T. Laarhoven . Sieving for shortest vectors in lattices using angular locality-sensitive hashing . In CRYPTO. 2015 . 5 [Laa15] T. Laarhoven. Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In CRYPTO. 2015. 5"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"e_1_2_1_58_1","volume-title":"ICALP.","author":"Lyubashevsky V.","year":"2006","unstructured":"[LM06] V. Lyubashevsky and D. Micciancio . Generalized compact knapsacks are collision resistant . In ICALP. 2006 . 16 [LM06] V. Lyubashevsky and D. Micciancio. Generalized compact knapsacks are collision resistant. In ICALP. 2006. 16"},{"key":"e_1_2_1_59_1","volume-title":"CRYPTO.","author":"Lyubashevsky V.","year":"2009","unstructured":"[LM09] V. Lyubashevsky and D. Micciancio . On bounded distance decoding, unique shortest vectors, and the minimum distance problem . In CRYPTO. 2009 . 15 [LM09] V. Lyubashevsky and D. Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In CRYPTO. 2009. 15"},{"key":"e_1_2_1_60_1","volume-title":"Finding shortest lattice vectors faster using quantum search. Des. Codes Cryptogr., 77(2--3):375--400","author":"Laarhoven T.","year":"2015","unstructured":"[LMvdP15] T. Laarhoven , M. Mosca , and J. van de Pol . Finding shortest lattice vectors faster using quantum search. Des. Codes Cryptogr., 77(2--3):375--400 , 2015 . 5 [LMvdP15] T. Laarhoven, M. Mosca, and J. van de Pol. Finding shortest lattice vectors faster using quantum search. Des. Codes Cryptogr., 77(2--3):375--400, 2015. 5"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.2461"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535925"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-014-9938-4"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.5"},{"key":"e_1_2_1_65_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0897-7","volume-title":"Complexity of lattice problems a cryptographic perspective","author":"Micciancio D.","year":"2002","unstructured":"[MG02] D. Micciancio and S. Goldwasser . Complexity of lattice problems a cryptographic perspective . Springer , 2002 . 1 [MG02] D. Micciancio and S. Goldwasser. Complexity of lattice problems a cryptographic perspective. Springer, 2002. 1"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700373039"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0234-9"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a022"},{"key":"e_1_2_1_69_1","volume-title":"CCC.","author":"Micciancio D.","year":"2014","unstructured":"[Mic14] D. Micciancio . Locally dense codes . In CCC. 2014 . 10 [Mic14] D. Micciancio. Locally dense codes. In CCC. 2014. 10"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a007"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447360"},{"key":"e_1_2_1_72_1","volume-title":"CRYPTO.","author":"Mukherjee T.","year":"2020","unstructured":"[MS20] T. Mukherjee and N. Stephens-Davidowitz . Lattice reduction for modules, or how to reduce modulesvp to modulesvp . In CRYPTO. 2020 . 17 [MS20] T. Mukherjee and N. Stephens-Davidowitz. Lattice reduction for modules, or how to reduce modulesvp to modulesvp. In CRYPTO. 2020. 17"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.09.002"},{"key":"e_1_2_1_74_1","first-page":"4","article-title":"Practical, predictable lattice basis reduction","author":"Micciancio D.","year":"2016","unstructured":"[MW16] D. Micciancio and M. Walter . Practical, predictable lattice basis reduction . In EUROCRYPT. 2016 . 4 , 14 [MW16] D. Micciancio and M. Walter. Practical, predictable lattice basis reduction. In EUROCRYPT. 2016. 4, 14","journal-title":"EUROCRYPT."},{"key":"e_1_2_1_75_1","volume-title":"Post-quantum cryptography project. https: \/\/csrc.nist.gov\/projects\/post-quantum-cryptography\/","author":"[Nat22] National Institute of Standards and Technology.","year":"2022","unstructured":"[Nat22] National Institute of Standards and Technology. Post-quantum cryptography project. https: \/\/csrc.nist.gov\/projects\/post-quantum-cryptography\/ , 2022 . 1 [Nat22] National Institute of Standards and Technology. Post-quantum cryptography project. https: \/\/csrc.nist.gov\/projects\/post-quantum-cryptography\/, 2022. 1"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0251-3"},{"key":"e_1_2_1_77_1","volume-title":"STOC.","author":"Peikert C.","year":"2009","unstructured":"[Pei09] C. Peikert . Public-key cryptosystems from the worst-case Shortest Vector Problem: extended abstract . In STOC. 2009 . 12 [Pei09] C. Peikert. Public-key cryptosystems from the worst-case Shortest Vector Problem: extended abstract. In STOC. 2009. 12"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000074"},{"key":"e_1_2_1_79_1","volume-title":"TCC.","author":"Peikert C.","year":"2006","unstructured":"[PR06] C. Peikert and A. Rosen . Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices . In TCC. 2006 . 16 [PR06] C. Peikert and A. Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In TCC. 2006. 16"},{"key":"e_1_2_1_80_1","volume-title":"STOC.","author":"Peikert C.","year":"2017","unstructured":"[PRS17] C. Peikert , O. Regev , and N. Stephens-Davidowitz . Pseudorandomness of Ring-LWE for any ring and modulus . In STOC. 2017 . 16 [PRS17] C. Peikert, O. Regev, and N. Stephens-Davidowitz. Pseudorandomness of Ring-LWE for any ring and modulus. In STOC. 2017. 16"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_2_1_82_1","first-page":"5","article-title":"Lattice problems and norm embeddings","author":"Regev O.","year":"2006","unstructured":"[RR06] O. Regev and R. Rosen . Lattice problems and norm embeddings . In STOC. 2006 . 5 , 7 [RR06] O. Regev and R. Rosen. Lattice problems and norm embeddings. In STOC. 2006. 5, 7","journal-title":"STOC."},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90064-8"},{"key":"e_1_2_1_84_1","volume-title":"Fast factoring integers by SVP algorithms. IACR Cryptol. ePrint Arch., page 232","author":"Schnorr C.","year":"2021","unstructured":"[Sch21a] C. Schnorr . Fast factoring integers by SVP algorithms. IACR Cryptol. ePrint Arch., page 232 , 2021 . 18 [Sch21a] C. Schnorr. Fast factoring integers by SVP algorithms. IACR Cryptol. ePrint Arch., page 232, 2021. 18"},{"key":"e_1_2_1_85_1","volume-title":"Fast factoring integers by SVP algorithms, corrected. IACR Cryptol. ePrint Arch., page 933","author":"Schnorr C.","year":"2021","unstructured":"[Sch21b] C. Schnorr . Fast factoring integers by SVP algorithms, corrected. IACR Cryptol. ePrint Arch., page 933 , 2021 . 18 [Sch21b] C. Schnorr. Fast factoring integers by SVP algorithms, corrected. IACR Cryptol. ePrint Arch., page 933, 2021. 18"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_87_1","volume-title":"Lattices and Beyond. Top 10 problems on algorithms and complexity aspects of lattices","author":"[Sim22] Simons Institute Summer Cluster","year":"2022","unstructured":"[Sim22] Simons Institute Summer Cluster : Lattices and Beyond. Top 10 problems on algorithms and complexity aspects of lattices , 2022 . Simons Institute Wiki Post . Available at https:\/\/wiki. simons.berkeley.edu\/doku.php?id=lat22:start. 1, 15 [Sim22] Simons Institute Summer Cluster: Lattices and Beyond. Top 10 problems on algorithms and complexity aspects of lattices, 2022. Simons Institute Wiki Post. Available at https:\/\/wiki. simons.berkeley.edu\/doku.php?id=lat22:start. 1, 15"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10366-7_36"},{"key":"e_1_2_1_89_1","volume-title":"APPROX.","author":"Stephens-Davidowitz N.","year":"2016","unstructured":"[Ste16] N. Stephens-Davidowitz . Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one . In APPROX. 2016 . 15 [Ste16] N. Stephens-Davidowitz. Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one. In APPROX. 2016. 15"},{"key":"e_1_2_1_90_1","volume-title":"Ring SIS and ideal lattices","author":"Stephens-Davidowitz N.","year":"2018","unstructured":"[Ste18] N. Stephens-Davidowitz . Ring SIS and ideal lattices , 2018 . Lecture notes. 17 [Ste18] N. Stephens-Davidowitz. Ring SIS and ideal lattices, 2018. Lecture notes. 17"},{"key":"e_1_2_1_91_1","volume-title":"FOCS.","author":"Sotiraki K.","year":"2018","unstructured":"[SZZ18] K. Sotiraki , M. Zampetakis , and G. Zirdelis . PPP-completeness with connections to cryptography . In FOCS. 2018 . 13 [SZZ18] K. Sotiraki, M. Zampetakis, and G. Zirdelis. PPP-completeness with connections to cryptography. In FOCS. 2018. 13"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.641542"},{"issue":"2","key":"e_1_2_1_94_1","doi-asserted-by":"crossref","first-page":"163","DOI":"10.2140\/moscow.2019.8.163","article-title":"Lattices with exponentially large kissing numbers","volume":"8","author":"S.","year":"2019","unstructured":"[Vl?a19] S. Vl?adut\u00b8 . Lattices with exponentially large kissing numbers . Mosc. J. Comb. Number Theory , 8 ( 2 ): 163 -- 177 , 2019 . 11 [Vl?a19] S. Vl?adut\u00b8. Lattices with exponentially large kissing numbers. Mosc. J. Comb. Number Theory, 8(2):163--177, 2019. 11","journal-title":"Mosc. J. Comb. Number Theory"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3586165.3586172","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3586165.3586172","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:12Z","timestamp":1750183692000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3586165.3586172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,28]]},"references-count":93,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2,28]]}},"alternative-id":["10.1145\/3586165.3586172"],"URL":"https:\/\/doi.org\/10.1145\/3586165.3586172","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2023,2,28]]},"assertion":[{"value":"2023-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}