{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T10:44:47Z","timestamp":1777632287334,"version":"3.51.4"},"reference-count":28,"publisher":"Wiley","issue":"A","license":[{"start":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T00:00:00Z","timestamp":1472169600000},"content-version":"unspecified","delay-in-days":238,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2016]]},"abstract":"Lattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving the SVP require space which (heuristically) grows as$2^{0.2075n+o(n)}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where$n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is the lattice dimension. In high dimensions, the memory requirement becomes a limiting factor for running these algorithms, making them uncompetitive with enumeration algorithms, despite their superior asymptotic time complexity.<\/jats:p>We generalize sieving algorithms to solve SVP with less memory. We consider reductions of tuples of vectors rather than pairs of vectors as existing sieve algorithms do. For triples, we estimate that the space requirement scales as$2^{0.1887n+o(n)}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. The naive algorithm for this triple sieve runs in time$2^{0.5661n+o(n)}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. With appropriate filtering of pairs, we reduce the time complexity to$2^{0.4812n+o(n)}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>while keeping the same space complexity. We further analyze the effects of using larger tuples for reduction, and conjecture how this provides a continuous trade-off between the memory-intensive sieving and the asymptotically slower enumeration.<\/jats:p>","DOI":"10.1112\/s1461157016000292","type":"journal-article","created":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T15:29:22Z","timestamp":1472225362000},"page":"146-162","source":"Crossref","is-referenced-by-count":39,"title":["Tuple lattice sieving"],"prefix":"10.1112","volume":"19","author":[{"given":"Shi","family":"Bai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thijs","family":"Laarhoven","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Damien","family":"Stehl\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2016,8,26]]},"reference":[{"key":"S1461157016000292_r12","first-page":"170","volume-title":"Proceedings of CRYPTO","author":"Hanrot","year":"2007"},{"key":"S1461157016000292_r9","first-page":"257","volume-title":"Proceedings of the EUROCRYPT","author":"Gama","year":"2010"},{"key":"S1461157016000292_r27","unstructured":"27. The\u00a0Sage Developers, \u2018Sage mathematics software (Version 6.8)\u2019, 2015, http:\/\/www.sagemath.org."},{"key":"S1461157016000292_r4","unstructured":"4. M. Albrecht , S. Bai , D. Cad\u00e9 , X. Pujol and D. Stehl\u00e9 , \u2018FPLLL-4.0, a floating-point LLL implementation\u2019, available at https:\/\/github.com\/dstehle\/fplll."},{"key":"S1461157016000292_r23","unstructured":"23. X. Pujol and D. Stehl\u00e9 , \u2018Solving the shortest lattice vector problem in time $2^{2.465n}$ \u2019, Cryptology ePrint Archive, Report 2009\/605, 2009, http:\/\/eprint.iacr.org\/2009\/605."},{"key":"S1461157016000292_r15","unstructured":"15. Inverse Symbolic Calculator, available at https:\/\/isc.carma.newcastle.edu.au\/index."},{"key":"S1461157016000292_r5","first-page":"10","volume-title":"Proceedings of the SODA","author":"Becker","year":"2016"},{"key":"S1461157016000292_r25","first-page":"181","volume-title":"Proceedings of the CALC","author":"Semaev","year":"2001"},{"key":"S1461157016000292_r24","unstructured":"24. O. Regev , \u2018Lecture notes of Lattices in Computer Science\u2019, taught at the Computer Science Tel Aviv University, available at http:\/\/www.cims.nyu.edu\/\u223cregev\/teaching\/lattices_fall_2004\/index.html."},{"key":"S1461157016000292_r3","unstructured":"3. M. Albrecht , \u2018DGS, an implementation of discrete Gaussians samplers over the integers\u2019, available at https:\/\/github.com\/malb\/dgs."},{"key":"S1461157016000292_r20","volume-title":"Proceedings\u00a0of SODA","author":"Micciancio","year":"2010"},{"key":"S1461157016000292_r13","unstructured":"13. G. Hanrot and D. Stehl\u00e9 , \u2018Worst-case Hermite\u2013Korkine\u2013Zolotarev reduced lattice bases\u2019, CoRR, Preprint, 2008, arXiv:0801.3331."},{"key":"S1461157016000292_r6","unstructured":"6. SVP Challenge. \u2018Svp challenge generator\u2019, available at http:\/\/latticechallenge.org\/svp-challenge."},{"key":"S1461157016000292_r17","first-page":"3","volume-title":"Proceedings of the CRYPTO","author":"Laarhoven","year":"2015"},{"key":"S1461157016000292_r18","first-page":"375","article-title":"Finding shortest lattice vectors faster using quantum search","volume":"77","author":"Laarhoven","year":"2015","journal-title":"DCC"},{"key":"S1461157016000292_r11","first-page":"159","volume-title":"IWCC","author":"Hanrot","year":"2011"},{"key":"S1461157016000292_r16","first-page":"99","volume-title":"Proceedings of the STOC","author":"Kannan","year":"1983"},{"key":"S1461157016000292_r10","first-page":"197","volume-title":"Proceedings of the STOC","author":"Gentry","year":"2008"},{"key":"S1461157016000292_r7","first-page":"1","volume-title":"Proceedings of the ASIACRYPT","author":"Chen","year":"2011"},{"key":"S1461157016000292_r8","first-page":"288","volume-title":"Proceedings of the LATINCRYPT","author":"Fitzpatrick","year":"2015"},{"key":"S1461157016000292_r26","first-page":"651","article-title":"On the reduction theory of positive quadratic forms","volume":"14","author":"Tammela","year":"1973","journal-title":"Sov. Math. Dokl."},{"key":"S1461157016000292_r2","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1145\/380752.380857","volume-title":"Proceedings of the STOC","author":"Ajtai","year":"2001"},{"key":"S1461157016000292_r28","unstructured":"28. Wolfram Research, Inc., Mathematica (version\u00a010.3), 2015."},{"key":"S1461157016000292_r1","first-page":"733","volume-title":"Proceedings of the STOC","author":"Aggarwal","year":"2015"},{"key":"S1461157016000292_r22","doi-asserted-by":"publisher","DOI":"10.1515\/JMC.2008.009"},{"key":"S1461157016000292_r14","first-page":"267","volume-title":"Proceedings of the ANTS","author":"Hoffstein","year":"1998"},{"key":"S1461157016000292_r21","doi-asserted-by":"publisher","DOI":"10.1145\/1597036.1597050"},{"key":"S1461157016000292_r19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88702-7_5"}],"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\/S1461157016000292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,19]],"date-time":"2023-08-19T21:29:06Z","timestamp":1692480546000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157016000292\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"references-count":28,"journal-issue":{"issue":"A","published-print":{"date-parts":[[2016]]}},"alternative-id":["S1461157016000292"],"URL":"https:\/\/doi.org\/10.1112\/s1461157016000292","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}