{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T12:22:26Z","timestamp":1742646146882,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,11,4]],"date-time":"2023-11-04T00:00:00Z","timestamp":1699056000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,4]],"date-time":"2023-11-04T00:00:00Z","timestamp":1699056000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62172405"],"award-info":[{"award-number":["62172405"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"abstract":"<jats:sec>\n                <jats:title>Abstract<\/jats:title>\n                <jats:p>Unique shortest vector problem (uSVP) plays an important role in lattice based cryptography. Many cryptographic schemes based their security on it. For the cofidence of those applications, it is essential to clarify the complexity of uSVP with different parameters. However, proving the NP-hardness of uSVP appears quite hard. To the state of the art, we are even not able to prove the NP-hardness of uSVP with constant parameters. In this work, we gave a lower bound for the hardness of uSVP with constant parameters, i.e. we proved that uSVP is at least as hard as gap shortest vector problem (GapSVP) with gap of <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n\/\\log (n)})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:mrow>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msqrt>\n                        <mml:mrow>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mo>\/<\/mml:mo>\n                          <mml:mo>log<\/mml:mo>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mo>)<\/mml:mo>\n                        <\/mml:mrow>\n                      <\/mml:msqrt>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is in <jats:inline-formula><jats:alternatives><jats:tex-math>$$NP \\cap coAM$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:mrow>\n                      <mml:mi>N<\/mml:mi>\n                      <mml:mi>P<\/mml:mi>\n                      <mml:mo>\u2229<\/mml:mo>\n                      <mml:mi>c<\/mml:mi>\n                      <mml:mi>o<\/mml:mi>\n                      <mml:mi>A<\/mml:mi>\n                      <mml:mi>M<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Unlike previous works, our reduction works for paramters in a bigger range, especially when the constant hidden by the big-<jats:italic>O<\/jats:italic> in GapSVP is smaller than 1.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Graphical abstract<\/jats:title>\n                \n              <\/jats:sec>","DOI":"10.1186\/s42400-023-00173-w","type":"journal-article","created":{"date-parts":[[2023,11,4]],"date-time":"2023-11-04T02:02:01Z","timestamp":1699063321000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved lower bound for the complexity of unique shortest vector problem"],"prefix":"10.1186","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6024-3635","authenticated-orcid":false,"given":"Baolong","family":"Jin","sequence":"first","affiliation":[]},{"given":"Rui","family":"Xue","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,11,4]]},"reference":[{"issue":"10","key":"173_CR1","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/j.ipl.2016.05.003","volume":"116","author":"D Aggarwal","year":"2016","unstructured":"Aggarwal D, Dubey CK (2016) Improved hardness results for unique shortest vector problem. Inf Process Lett 116(10):631\u2013637. https:\/\/doi.org\/10.1016\/j.ipl.2016.05.003","journal-title":"Inf Process Lett"},{"key":"173_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai M (1996) Generating hard instances of lattice problems (extended abstract). In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, STOC \u201996 New York, pp 99\u2013108","DOI":"10.1145\/237814.237838"},{"key":"173_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai M (1998) The shortest vector problem in l2 is np-hard for randomized reductions (extended abstract). In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, STOC \u201998 New York, pp 10\u201319","DOI":"10.1145\/276698.276705"},{"key":"173_CR4","doi-asserted-by":"crossref","unstructured":"Ajtai M, Dwork C (1997) A public-key cryptosystem with worst-case\/average-case equivalence. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, STOC \u201997 New York, pp 284\u2013293","DOI":"10.1145\/258533.258604"},{"key":"173_CR5","unstructured":"Boas P (1981) Another NP-complete partition problem and the complexity of computing short vectors in a lattice. https:\/\/staff.fnwi.uva.nl\/p.vanemdeboas\/vectors\/mi8104c.html"},{"issue":"1","key":"173_CR6","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0304-3975(98)00058-9","volume":"207","author":"J Cai","year":"1998","unstructured":"Cai J (1998) A relation of primal-dual lattices and the complexity of shortest lattice vector problem. Theor Comput Sci 207(1):105\u2013116. https:\/\/doi.org\/10.1016\/S0304-3975(98)00058-9","journal-title":"Theor Comput Sci"},{"issue":"1\u20132","key":"173_CR7","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1006\/inco.1998.2762","volume":"151","author":"J Cai","year":"1999","unstructured":"Cai J, Cusick TW (1999) A lattice-based public-key cryptosystem. Inf Comput 151(1\u20132):17\u201331. https:\/\/doi.org\/10.1006\/inco.1998.2762","journal-title":"Inf Comput"},{"issue":"3","key":"173_CR8","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1006\/jcss.1999.1686","volume":"60","author":"O Goldreich","year":"2000","unstructured":"Goldreich O, Goldwasser S (2000) On the limits of nonapproximability of lattice problems. J Comput Syst Sci 60(3):540\u2013563. https:\/\/doi.org\/10.1006\/jcss.1999.1686","journal-title":"J Comput Syst Sci"},{"key":"173_CR9","unstructured":"Khoat TQ, Tan NH (2008) Unique shortest vector problem for max norm is NP-hard. Cryptology ePrint Archive, Paper 2008\/366. https:\/\/eprint.iacr.org\/2008\/366"},{"key":"173_CR10","unstructured":"Khot S (2003) Hardness of approximating the shortest vector problem in high $$l_p$$ norms. , In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. pp 290\u2013297"},{"key":"173_CR11","doi-asserted-by":"crossref","unstructured":"Khot S (2004) Hardness of approximating the shortest vector problem in lattices. In: 45th Annual IEEE Symposium on Foundations of Computer Science pp 126\u2013135","DOI":"10.1109\/FOCS.2004.31"},{"issue":"1\u20132","key":"173_CR12","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1016\/S0304-3975(00)00387-X","volume":"255","author":"R Kumar","year":"2001","unstructured":"Kumar R, Sivakumar D (2001) On the unique shortest lattice vector problem. Theor Comput Sci 255(1\u20132):641\u2013648. https:\/\/doi.org\/10.1016\/S0304-3975(00)00387-X","journal-title":"Theor Comput Sci"},{"key":"173_CR13","unstructured":"Liu M, Wang X, Xu G, Zheng X (2011) Shortest lattice vectors in the presence of gaps. Cryptology ePrint Archive, Paper 2011\/139. https:\/\/eprint.iacr.org\/2011\/139"},{"key":"173_CR14","unstructured":"Lyubashevsky V (2008) The $$n^c$$-unique shortest vector problem is hard. Cryptology ePrint Archive, Paper 2008\/504. https:\/\/eprint.iacr.org\/2008\/504"},{"key":"#cr-split#-173_CR15.1","doi-asserted-by":"crossref","unstructured":"Lyubashevsky V, Micciancio D (2009) On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Halevi S","DOI":"10.1007\/978-3-642-03356-8_34"},{"key":"#cr-split#-173_CR15.2","unstructured":"(ed) Advances in cryptology - CRYPTO 2009. Lecture Notes in Computer Science Berlin, vol 5677, Springer, Heidelberg, pp 577-594"},{"key":"173_CR16","doi-asserted-by":"crossref","unstructured":"Micciancio D (1998) The shortest vector in a lattice is hard to approximate to within some constant. , In: Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pp 92\u201398","DOI":"10.1109\/SFCS.1998.743432"},{"issue":"1","key":"173_CR17","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1137\/S0097539703433511","volume":"34","author":"D Micciancio","year":"2004","unstructured":"Micciancio D (2004) Almost perfect lattices, the covering radius problem, and applications to ajtai\u2019s connection factor. SIAM J Comput 34(1):118\u2013169. https:\/\/doi.org\/10.1137\/S0097539703433511","journal-title":"SIAM J Comput"},{"issue":"1","key":"173_CR18","doi-asserted-by":"publisher","first-page":"487","DOI":"10.4086\/toc.2012.v008a022","volume":"8","author":"D Micciancio","year":"2012","unstructured":"Micciancio D (2012) Inapproximability of the shortest vector problem: toward a deterministic reduction. Theory Comput 8(1):487\u2013512. https:\/\/doi.org\/10.4086\/toc.2012.v008a022","journal-title":"Theory Comput"},{"key":"173_CR19","doi-asserted-by":"crossref","unstructured":"Peikert C (2009) Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, STOC \u201909 New York, pp 333\u2013342","DOI":"10.1145\/1536414.1536461"},{"key":"173_CR20","doi-asserted-by":"crossref","unstructured":"Regev O (2003) New lattice based cryptographic constructions. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, STOC \u201903 New York, pp 407\u2013416","DOI":"10.1145\/780542.780603"},{"issue":"1","key":"173_CR21","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer N (1972) On the density of families of sets. J Comb Theory Ser A 13(1):145\u2013147. https:\/\/doi.org\/10.1016\/0097-3165(72)90019-2","journal-title":"J Comb Theory Ser A"},{"key":"173_CR22","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"Shelah S (1972) A combinatorial problem; stability and order for models and theories in infinitary languages. Pac J Math 41:247\u2013261. https:\/\/doi.org\/10.2140\/pjm.1972.41.247","journal-title":"Pac J Math"},{"key":"173_CR23","unstructured":"Stephens-Davidowitz N (2016) Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one. In: Jansen K, Mathieu C, Rolim JDP, Umans C (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2016). vol. 60, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Leibniz International Proceedings in Informatics (LIPIcs) Dagstuhl, Germany, pp. 19\u201311918"},{"key":"173_CR24","first-page":"11","volume-title":"On the uniform convergence of relative frequencies of events to their probabilities","author":"VN Vapnik","year":"2015","unstructured":"Vapnik VN, Chervonenkis AY (2015) On the uniform convergence of relative frequencies of events to their probabilities. Springer, Cham, pp 11\u201330"},{"key":"173_CR25","doi-asserted-by":"crossref","unstructured":"Wei W, Liu M, Wang X (2015) Finding shortest lattice vectors in the presence of gaps. In: Nyberg K (ed), Topics in cryptology\u2014CT-RSA 2015 Cham, Springer, pp 239\u2013257","DOI":"10.1007\/978-3-319-16715-2_13"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-023-00173-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-023-00173-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-023-00173-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,4]],"date-time":"2023-11-04T02:02:54Z","timestamp":1699063374000},"score":1,"resource":{"primary":{"URL":"https:\/\/cybersecurity.springeropen.com\/articles\/10.1186\/s42400-023-00173-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,4]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["173"],"URL":"https:\/\/doi.org\/10.1186\/s42400-023-00173-w","relation":{},"ISSN":["2523-3246"],"issn-type":[{"type":"electronic","value":"2523-3246"}],"subject":[],"published":{"date-parts":[[2023,11,4]]},"assertion":[{"value":"30 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"38"}}