{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:22:21Z","timestamp":1740122541106,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T00:00:00Z","timestamp":1666051200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T00:00:00Z","timestamp":1666051200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["628.001.028","016.Veni.192.005"],"award-info":[{"award-number":["628.001.028","016.Veni.192.005"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The main idea behind lattice sieving algorithms is to reduce a sufficiently large number of lattice vectors with each other so that a set of short enough vectors is obtained. It is therefore natural to study vectors which cannot be reduced. In this work we give a concrete definition of an irreducible vector and study the properties of the set of all such vectors. We show that the set of irreducible vectors is a subset of the set of Voronoi relevant vectors and study its properties. For extremal lattices this set may contain as many as <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> vectors, which leads us to define the notion of a complete system of irreducible vectors, whose size can be upper-bounded by the kissing number. One of our main results shows that modified heuristic sieving algorithms heuristically approximate such a set (modulo sign). We provide experiments in low dimensions which support this theory. Finally we give some applications of this set in the study of lattice problems such as SVP, SIVP and CVPP. The introduced notions, as well as various results derived along the way, may provide further insights into lattice algorithms and motivate new research into understanding these algorithms better.<\/jats:p>","DOI":"10.1007\/s10623-022-01119-y","type":"journal-article","created":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T11:04:08Z","timestamp":1666091048000},"page":"609-643","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The irreducible vectors of a lattice:"],"prefix":"10.1007","volume":"91","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0437-1525","authenticated-orcid":false,"given":"Emmanouil","family":"Doulgerakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thijs","family":"Laarhoven","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benne","family":"de Weger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,18]]},"reference":[{"issue":"8","key":"1119_CR1","doi-asserted-by":"publisher","first-page":"2201","DOI":"10.1109\/TIT.2002.800499","volume":"48","author":"E Agrell","year":"2002","unstructured":"Agrell E., Eriksson T., Vardy A., Zeger K.: Closest point search in lattices. Trans. Inform. Theory 48(8), 2201\u20132214 (2002).","journal-title":"Trans. Inform. Theory"},{"key":"1119_CR2","doi-asserted-by":"crossref","unstructured":"Albrecht M., Ducas L., Herold G., Kirshanova E., Postlethwaite E., Stevens M.: The general sieve kernel and new records in lattice reduction. In: Proceedings of the 38th EUROCRYPT, pp. 717\u2013746. Springer, New York (2019).","DOI":"10.1007\/978-3-030-17656-3_25"},{"issue":"A","key":"1119_CR3","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1112\/S1461157016000292","volume":"19","author":"S Bai","year":"2016","unstructured":"Bai S., Laarhoven T., Stehl\u00e9 D.: Tuple lattice sieving. LMS J. Comput. Math. 19(A), 146\u2013162 (2016).","journal-title":"LMS J. Comput. Math."},{"key":"1119_CR4","doi-asserted-by":"crossref","unstructured":"Bonifas N., Dadush D.: Short paths on the Voronoi graph and the closest vector problem with preprocessing. In: Proceedings of the 26th SODA, pp. 295\u2013314. ACM-SIAM, New York (2015).","DOI":"10.1137\/1.9781611973730.22"},{"key":"1119_CR5","doi-asserted-by":"crossref","unstructured":"Cabeleira F., Mariano A., Falcao G.: Memory-optimized Voronoi cell-based parallel kernels for the shortest vector problem on lattices. In: Proceedings of the 27th EUSIPCO, pp. 1\u20135. IEEE (2019).","DOI":"10.23919\/EUSIPCO.2019.8902635"},{"key":"1119_CR6","doi-asserted-by":"crossref","unstructured":"Chen Y., Nguyen P.Q.: BKZ 2.0: better lattice security estimates. In: Proceedings of the 17th ASIACRYPT, pp. 1\u201320. Springer, New York (2011).","DOI":"10.1007\/978-3-642-25385-0_1"},{"key":"1119_CR7","doi-asserted-by":"crossref","unstructured":"Conway J.H., Sloane N.J.: Low-dimensional lattices. VI. Voronoi reduction of three-dimensional lattices. In: Proceedings of the Mathematical and Physical Sciences, vol. 436, pp. 55\u201368. The Royal Society (1992).","DOI":"10.1098\/rspa.1992.0004"},{"key":"1119_CR8","volume-title":"Sphere packings, lattices and groups","author":"JH Conway","year":"1998","unstructured":"Conway J.H., Sloane N.J.: Sphere packings, lattices and groups. Springer, New York (1998)."},{"key":"1119_CR9","unstructured":"The Sage Developers: Sagemath, the Sage Mathematics Software System. https:\/\/www.sagemath.org (2019)."},{"key":"1119_CR10","doi-asserted-by":"crossref","unstructured":"Doulgerakis E., Laarhoven T., de\u00a0Weger B.: Finding closest lattice vectors using approximate Voronoi cells. In: Proceedings of the 10th PQCRYPTO, pp. 3\u201322. Springer, New York (2019).","DOI":"10.1007\/978-3-030-25510-7_1"},{"key":"1119_CR11","doi-asserted-by":"crossref","unstructured":"Ducas L., Laarhoven T., van Woerden W.: The randomized slicer for CVPP: sharper, faster, smaller, batchier. In: Proceedings of the 23rd PKC, pp. 3\u201336. Springer, New York (2020).","DOI":"10.1007\/978-3-030-45388-6_1"},{"key":"1119_CR12","unstructured":"Elkies N.: Theta functions and weighted theta functions of euclidean lattices, with some applications. http:\/\/people.math.harvard.edu\/~elkies\/aws09.pdf (2009)."},{"key":"1119_CR13","doi-asserted-by":"publisher","first-page":"127012","DOI":"10.1109\/ACCESS.2019.2939142","volume":"7","author":"G Falcao","year":"2019","unstructured":"Falcao G., Cabeleira F., Mariano A., Paulo Santos L.: Heterogeneous implementation of a Voronoi cell-based SVP solver. IEEE Access 7, 127012\u2013127023 (2019).","journal-title":"IEEE Access"},{"key":"1119_CR14","doi-asserted-by":"crossref","unstructured":"Gama N., Nguyen P.Q., Regev O.: Lattice enumeration using extreme pruning. In: Proceedings of the 29th EUROCRYPT, pp. 257\u2013278. Springer, New York (2010).","DOI":"10.1007\/978-3-642-13190-5_13"},{"issue":"2","key":"1119_CR15","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/j.1538-7305.1950.tb00463.x","volume":"29","author":"R Hamming","year":"1950","unstructured":"Hamming R.: Error detecting and error correcting codes. Bell Syst. Tech. J. 29(2), 147\u2013160 (1950).","journal-title":"Bell Syst. Tech. J."},{"key":"1119_CR16","unstructured":"Hopkins M.: Representation-theoretic techniques for independence bounds of Cayley graphs. Bachelor thesis (2018)."},{"key":"1119_CR17","doi-asserted-by":"crossref","unstructured":"Hunkenschr\u00f6der C., Reuland G., Schymura M.: On compact representations of Voronoi cells of lattices. In: Proceedings of the 20th IPCO, Lecture Notes in Computer Science, vol. 11480, pp. 261\u2013274. Springer, Berlin (2019).","DOI":"10.1007\/978-3-030-17953-3_20"},{"key":"1119_CR18","first-page":"3","volume":"14","author":"G Kabatiansky","year":"1978","unstructured":"Kabatiansky G., Levenshtein V.: Bounds for packings on a sphere and in space. Problemy Peredachi Informatsii 14, 3\u201325 (1978).","journal-title":"Problemy Peredachi Informatsii"},{"key":"1119_CR19","doi-asserted-by":"crossref","unstructured":"Laarhoven T.: Sieving for closest lattice vectors (with preprocessing). In: Proceedings of the 23rd SAC, pp. 523\u2013542. Springer, Berlin (2016).","DOI":"10.1007\/978-3-319-69453-5_28"},{"issue":"4","key":"1119_CR20","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra A.K., Lenstra H.W. Jr., Lov\u00e1sz L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982).","journal-title":"Math. Ann."},{"issue":"4","key":"1119_CR21","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986).","journal-title":"SIAM J. Comput."},{"key":"1119_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0897-7","volume-title":"Complexity of Lattice Problems: A Cryptographic Perspective","author":"D Micciancio","year":"2002","unstructured":"Micciancio D., Goldwasser S.: Complexity of Lattice Problems: A Cryptographic Perspective. Kluwer Academic Publishers, Boston (2002)."},{"key":"1119_CR23","doi-asserted-by":"crossref","unstructured":"Micciancio D., Voulgaris P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: Proceedings of the 42nd STOC, pp. 351\u2013358. ACM Press, New York (2010).","DOI":"10.1145\/1806689.1806739"},{"key":"1119_CR24","doi-asserted-by":"crossref","unstructured":"Micciancio D., Voulgaris P.: Faster exponential time algorithms for the shortest vector problem. In: Proceedings of the 21st SODA, pp. 1468\u20131480. ACM-SIAM, New York (2010).","DOI":"10.1137\/1.9781611973075.119"},{"key":"1119_CR25","unstructured":"Minkowski H.: In: Gesammelte Abhandlungen von Hermann Minkowski, vol.\u00a02, pp. 103\u2013121 (1911)."},{"key":"1119_CR26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon J.W., Moser L.: On cliques in graphs. Israel J. Math. 3, 23\u201328 (1965).","journal-title":"Israel J. Math."},{"issue":"4","key":"1119_CR27","doi-asserted-by":"publisher","first-page":"46:1","DOI":"10.1145\/1597036.1597050","volume":"5","author":"PQ Nguyen","year":"2009","unstructured":"Nguyen P.Q., Stehl\u00e9 D.: Low-dimensional lattice basis reduction revisited. ACM Trans. Algorith. 5(4), 46:1-46:48 (2009).","journal-title":"ACM Trans. Algorith."},{"issue":"2","key":"1119_CR28","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1515\/JMC.2008.009","volume":"2","author":"PQ Nguyen","year":"2008","unstructured":"Nguyen P.Q., Vidick T.: Sieve algorithms for the shortest vector problem are practical. J. Math. Cryptol. 2(2), 181\u2013207 (2008).","journal-title":"J. Math. Cryptol."},{"key":"1119_CR29","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0012-365X(95)00239-S","volume":"161","author":"DS Rajan","year":"1996","unstructured":"Rajan D.S., Shende A.M.: A characterization of root lattices. Discret. Math. 161, 309\u2013314 (1996).","journal-title":"Discret. Math."},{"key":"1119_CR30","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/BF02759743","volume":"2","author":"M Rosenfeld","year":"1964","unstructured":"Rosenfeld M.: Independent sets in regular graphs. Israel J. Math. 2, 262\u2013272 (1964).","journal-title":"Israel J. Math."},{"issue":"2","key":"1119_CR31","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1137\/060676362","volume":"23","author":"N Sommer","year":"2009","unstructured":"Sommer N., Feder M., Shalvi O.: Finding the closest lattice point by iterative slicing. SIAM J. Discret. Math. 23(2), 715\u2013731 (2009).","journal-title":"SIAM J. Discret. Math."},{"key":"1119_CR32","unstructured":"SURFsara: The Lisa cluster. https:\/\/userinfo.surfsara.nl\/systems\/lisa (2019)."},{"key":"1119_CR33","unstructured":"The FPLLL development team: fplll, a lattice reduction library. https:\/\/github.com\/fplll\/fplll (2019)."},{"key":"1119_CR34","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1109\/18.481786","volume":"42","author":"E Viterbo","year":"1996","unstructured":"Viterbo E., Biglieri E.: Computing the Voronoi cell of a lattice: the diamond-cutting algorithm. IEEE Trans. Inform. Theory 42, 161\u2013171 (1996).","journal-title":"IEEE Trans. Inform. Theory"},{"key":"1119_CR35","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1515\/crll.1908.134.198","volume":"134","author":"G Voronoi","year":"1908","unstructured":"Voronoi G.: Nouvelles applications des param\u00e8tres continus \u00e0 la th\u00e9orie des formes quadratiques. deuxi\u00e8me m\u00e9moire. recherches sur les parall\u00e9llo\u00e8dres primitifs. J. Reine Angew. Math. 134, 198\u2013287 (1908).","journal-title":"J. Reine Angew. Math."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01119-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-022-01119-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01119-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T07:51:45Z","timestamp":1676015505000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-022-01119-y"}},"subtitle":["Some theory and applications"],"short-title":[],"issued":{"date-parts":[[2022,10,18]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1119"],"URL":"https:\/\/doi.org\/10.1007\/s10623-022-01119-y","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"type":"print","value":"0925-1022"},{"type":"electronic","value":"1573-7586"}],"subject":[],"published":{"date-parts":[[2022,10,18]]},"assertion":[{"value":"13 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}