{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T02:35:20Z","timestamp":1790044520083,"version":"4.0.1"},"reference-count":39,"publisher":"Wiley","issue":"A","license":[{"start":{"date-parts":[[2014,8,1]],"date-time":"2014-08-01T00:00:00Z","timestamp":1406851200000},"content-version":"unspecified","delay-in-days":212,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2014]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie in overlattices or translated cosets of overlattices. The key idea is hence no longer to work with a single lattice but to move the problems around in a tower of related lattices. We initiate the algorithm by sampling very short vectors in an overlattice of the original lattice that admits a quasi-orthonormal basis and hence an efficient enumeration of vectors of bounded norm. Taking sums of vectors in the sample, we construct short vectors in the next lattice. Finally, we obtain solution vector(s) in the initial lattice as a sum of vectors of an overlattice. The complexity analysis relies on the Gaussian heuristic. This heuristic is backed by experiments in low and high dimensions that closely reflect these estimates when solving hard lattice problems in the average case.<\/jats:p><jats:p>This new approach allows us to solve not only shortest vector problems, but also closest vector problems, in lattices of dimension<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000229_inline1\"\/><jats:tex-math>$\\def \\xmlpi #1{}\\def \\mathsfbi #1{\\boldsymbol {\\mathsf {#1}}}\\let \\le =\\leqslant \\let \\leq =\\leqslant \\let \\ge =\\geqslant \\let \\geq =\\geqslant \\def \\Pr {\\mathit {Pr}}\\def \\Fr {\\mathit {Fr}}\\def \\Rey {\\mathit {Re}}n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>in time<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000229_inline2\"\/><jats:tex-math>$2^{0.3774\\, n}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>using memory<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000229_inline3\"\/><jats:tex-math>$2^{0.2925\\, n}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Moreover, the algorithm is straightforward to parallelize on most computer architectures.<\/jats:p>","DOI":"10.1112\/s1461157014000229","type":"journal-article","created":{"date-parts":[[2014,8,5]],"date-time":"2014-08-05T10:34:15Z","timestamp":1407234855000},"page":"49-70","source":"Crossref","is-referenced-by-count":29,"title":["A sieve algorithm based on overlattices"],"prefix":"10.1112","volume":"17","author":[{"given":"Anja","family":"Becker","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicolas","family":"Gama","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antoine","family":"Joux","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2014,8,1]]},"reference":[{"key":"S1461157014000229_r2","doi-asserted-by":"crossref","unstructured":"2. M. Ajtai , \u2018Random lattices and a conjectured 0\u20131 law about their polynomial time computable properties\u2019, Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS\u00a0\u201902 (IEEE Computer Society, 2002) 733\u2013742.","DOI":"10.1109\/SFCS.2002.1181998"},{"key":"S1461157014000229_r32","unstructured":"32. \u2018OpenMP Architecture Review Board, OpenMP API version 4.0\u2019, 2013."},{"key":"S1461157014000229_r5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_31"},{"key":"S1461157014000229_r12","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjjip.20.785"},{"key":"S1461157014000229_r6","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00341-3"},{"key":"S1461157014000229_r4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20465-4_21"},{"key":"S1461157014000229_r11","unstructured":"11. T.\u00a0G. et al., \u2018GNU multiple precision arithmetic library 5.1.3\u2019, September 2013, https:\/\/gmplib.org\/."},{"key":"S1461157014000229_r14","unstructured":"14. N. Gama , M. Izabachene , P.\u00a0Q. Nguyen and X. Xie , \u2018Structural lattice reduction: generalized worst-case to average-case reductions\u2019, Cryptology ePrint Archive, Report 2014\/283, 2014."},{"key":"S1461157014000229_r36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581144"},{"key":"S1461157014000229_r13","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_7"},{"key":"S1461157014000229_r15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_13"},{"key":"S1461157014000229_r3","doi-asserted-by":"crossref","unstructured":"3. M. Ajtai , R. Kumar and D. Sivakumar , \u2018A sieve algorithm for the shortest lattice vector problem\u2019, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201901 (ACM Press, 2001) 601\u2013610.","DOI":"10.1145\/380752.380857"},{"key":"S1461157014000229_r9","first-page":"155","volume-title":"Advances in cryptology \u2014 EUROCRYPT 1996","author":"Coppersmith","year":"1996"},{"key":"S1461157014000229_r10","first-page":"99","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS \u201998","author":"Dinur","year":"1998"},{"key":"S1461157014000229_r16","unstructured":"16. N. Gama , J. van\u00a0de Pol and J.\u00a0M. Schanck , \u2018Fork of V. Shoup\u2019s number theory library NTL, with improved lattice functionalities\u2019, February 2013, http:\/\/www.prism.uvsq.fr\/\u223cgama\/newntl.html."},{"key":"S1461157014000229_r18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74143-5_10"},{"key":"S1461157014000229_r37","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1307\/mmj\/1030132184","article-title":"Higher-dimensional analogs of Hermite\u2019s constant","volume":"45","author":"Thunder","year":"1998","journal-title":"Michigan Math. J."},{"key":"S1461157014000229_r19","doi-asserted-by":"crossref","unstructured":"19. T. Ishiguro , S. Kiyomoto , Y. Miyake and T. Takagi , \u2018Parallel Gauss sieve algorithm: solving the SVP in the ideal lattice of 128-dimensions\u2019, Cryptology ePrint Archive, Report 2013\/388, 2013.","DOI":"10.1007\/978-3-642-54631-0_24"},{"key":"S1461157014000229_r20","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900042"},{"key":"S1461157014000229_r21","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808749"},{"key":"S1461157014000229_r23","first-page":"336","article-title":"Sur les formes quadratiques","volume":"6","author":"Korkine","year":"1973","journal-title":"Math. Ann."},{"key":"S1461157014000229_r24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"S1461157014000229_r25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25385-0_6"},{"key":"S1461157014000229_r26","first-page":"92","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS \u201998","author":"Micciancio","year":"1998"},{"key":"S1461157014000229_r27","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806739"},{"key":"S1461157014000229_r28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.119"},{"key":"S1461157014000229_r29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23178-0_40"},{"key":"S1461157014000229_r30","first-page":"248","article-title":"On some arithmetical results in the geometry of numbers","volume":"1","author":"Mordell","year":"1935","journal-title":"Compos. Math."},{"key":"S1461157014000229_r31","doi-asserted-by":"publisher","DOI":"10.1515\/JMC.2008.009"},{"key":"S1461157014000229_r34","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-28.3.309"},{"key":"S1461157014000229_r35","unstructured":"35. M. Schneider , N. Gama , P. Baumann and P. Nobach , http:\/\/www.latticechallenge.org\/svp-challenge\/halloffame.php."},{"key":"S1461157014000229_r38","first-page":"1","volume-title":"Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security, ASIACCS \u201911","author":"Wang","year":"2011"},{"key":"S1461157014000229_r7","unstructured":"7. X. Cad\u00e9 , D. Pujol and D. Stehl\u00e9 , fplll 4.0.4, May 2013."},{"key":"S1461157014000229_r33","unstructured":"33. X. Pujol and D. Stehl\u00e9 , \u2018Solving the shortest lattice vector problem in time $2^{2.465n}$ \u2019, IACR Cryptology ePrint Archive 2009\/605, 2009."},{"key":"S1461157014000229_r22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"S1461157014000229_r17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22792-9_25"},{"key":"S1461157014000229_r8","first-page":"178","volume-title":"Advances in cryptology \u2014 EUROCRYPT 1996","author":"Coppersmith","year":"1996"},{"key":"S1461157014000229_r1","doi-asserted-by":"crossref","unstructured":"1. M. Ajtai , \u2018The shortest vector problem in ${L}_2$ is NP-hard for randomized reductions (extended abstract)\u2019, Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201998 (ACM Press, 1998) 10\u201319.","DOI":"10.1145\/276698.276705"},{"key":"S1461157014000229_r39","volume-title":"Selected areas in cryptography \u2014 SAC 2013","author":"Zhang","year":"2014"}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157014000229","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,13]],"date-time":"2019-08-13T15:28:51Z","timestamp":1565710131000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157014000229\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"references-count":39,"journal-issue":{"issue":"A","published-print":{"date-parts":[[2014]]}},"alternative-id":["S1461157014000229"],"URL":"https:\/\/doi.org\/10.1112\/s1461157014000229","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}