{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:24:27Z","timestamp":1787333067276,"version":"build-2736575974"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100019827","name":"Meta Platforms, Inc.","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100019827","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A lattice of integers is the collection of all linear combinations of a set of vectors for which all entries of the vectors are integers and all coefficients in the linear combinations are also integers. Lattice reduction refers to the problem of finding a set of vectors in a given lattice such that the collection of all integer linear combinations of this subset is still the entire original lattice and so that the Euclidean norms of the subset are reduced. The present paper proposes simple, efficient iterations for lattice reduction which are guaranteed to reduce the Euclidean norms of the basis vectors (the vectors in the subset) monotonically during every iteration. Each iteration selects the basis vector for which projecting off (with integer coefficients) the components of the other basis vectors along the selected vector minimizes the Euclidean norms of the reduced basis vectors. Each iteration projects off the components along the selected basis vector and efficiently updates all information required for the next iteration to select its best basis vector and perform the associated projections.<\/jats:p>","DOI":"10.1137\/23m1557933","type":"journal-article","created":{"date-parts":[[2024,1,24]],"date-time":"2024-01-24T04:02:21Z","timestamp":1706068941000},"page":"353-367","source":"Crossref","is-referenced-by-count":3,"title":["An Efficient Algorithm for Integer Lattice Reduction"],"prefix":"10.1137","volume":"45","author":[{"given":"Fran\u00e7ois","family":"Charton","sequence":"first","affiliation":[{"name":"Meta Platforms, 6 Rue M\u00e9nars 75002, Paris, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kristin","family":"Lauter","sequence":"additional","affiliation":[{"name":"Meta Platforms, Seattle, WA 98109 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cathy","family":"Li","sequence":"additional","affiliation":[{"name":"Meta Platforms, Seattle, WA 98109 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Tygert","sequence":"additional","affiliation":[{"name":"Meta Platforms, Menlo Park, CA 94025-2440 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,1,24]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01445125"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/567806.567807"},{"key":"ref3","series-title":"Pure Appl. Math. (Boca Raton)","volume-title":"Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications","author":"Bremner M. R.","year":"2012"},{"key":"ref4","series-title":"Classics Math.","volume-title":"An Introduction to the Geometry of Numbers","author":"Cassels J. W. S.","year":"1997"},{"key":"ref5","series-title":"Seminumerical Algorithms","volume-title":"Art of Computer Programming","volume":"2","author":"Knuth D. E.","year":"1998","edition":"3"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/355841.355847"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1839"},{"key":"ref9","unstructured":"C. Y. Li, J. Sot\u00e1kov\u00e1, E. Wenger, Z. Allen-Zhu, F. Charton, and K. Lauter, SALSA VERDE: A Machine Learning Attack on Learning with Errors with Sparse Small Secrets, Technical report 968, Cryptology ePrint Archive, https:\/\/eprint.iacr.org\/2023\/968, 2023."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02295-1"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1561\/0400000074"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581144"},{"key":"ref14","series-title":"Inf. Sec. Cryptography","first-page":"179","volume-title":"The LLL Algorithm: Survey and Applications","author":"Stehl\u00e9 D.","year":"2010"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1557933","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:29:30Z","timestamp":1787329770000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1557933"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,24]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/23M1557933"],"URL":"https:\/\/doi.org\/10.1137\/23m1557933","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,24]]}}}