{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T01:06:17Z","timestamp":1759799177200,"version":"build-2065373602"},"reference-count":23,"publisher":"International Association for Cryptologic Research","issue":"3","license":[{"start":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T00:00:00Z","timestamp":1751846400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,9,2]]},"abstract":"<jats:p>        Most concrete analyses of lattice reduction focus on the BKZ algorithm or its variants relying on Shortest Vector Problem (SVP) oracles. However, a variant by Li and Nguyen (Cambridge U. Press 2014) exploits more powerful oracles, namely for the Densest rank-<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>k<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math> Sublattice Problem (DSP<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:msub>\n                  <mml:mi\/>\n                  <mml:mi>k<\/mml:mi>\n                <\/mml:msub>\n              <\/mml:mrow>\n            <\/mml:math>) for <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>k<\/mml:mi>\n                <mml:mo>\u2265<\/mml:mo>\n                <mml:mn>2<\/mml:mn>\n              <\/mml:mrow>\n            <\/mml:math>.                  We first observe that, for random lattices, DSP<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:msub>\n                  <mml:mi\/>\n                  <mml:mn>2<\/mml:mn>\n                <\/mml:msub>\n              <\/mml:mrow>\n            <\/mml:math> \u2013and possibly even DSP<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:msub>\n                  <mml:mi\/>\n                  <mml:mn>3<\/mml:mn>\n                <\/mml:msub>\n              <\/mml:mrow>\n            <\/mml:math>\u2013 seems heuristically not much more expensive than solving SVP with the current best algorithm. We indeed argue that a densest sublattice can be found among pairs or triples of vectors produced by lattice sieving, at a negligible additional cost. This gives hope that this approach could be competitive.                  We therefore proceed to a heuristic and average-case analysis of the slope of DSP<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:msub>\n                  <mml:mi\/>\n                  <mml:mi>k<\/mml:mi>\n                <\/mml:msub>\n              <\/mml:mrow>\n            <\/mml:math>-BKZ output, inspired by a theorem of Kim (Journal of Number Theory 2022) which suggest a prediction for the volume of the densest rank-<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>k<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math> sublattice of a random lattice.                  Under this heuristic, the slope for <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>k<\/mml:mi>\n                <mml:mo>=<\/mml:mo>\n                <mml:mn>2<\/mml:mn>\n              <\/mml:mrow>\n            <\/mml:math> or <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mn>3<\/mml:mn>\n              <\/mml:mrow>\n            <\/mml:math> appears tenuously better than that of BKZ, making this approach less effective than regular BKZ using the \u201cDimensions for Free\u201d of Ducas (EUROCRYPT 2018). Furthermore, our experiments show that this heuristic is overly optimistic.                  Despite the hope raised by our first observation, we therefore conclude that this approach appears to be a No-Go for cryptanalysis of generic lattice problems.          <\/jats:p>","DOI":"10.62056\/ae0fhsfg","type":"journal-article","created":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T18:49:52Z","timestamp":1759776592000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Lattice Reduction via Dense Sublattices: A Cryptanalytic No-Go"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2510-4829","authenticated-orcid":false,"given":"Leo","family":"Ducas","sequence":"first","affiliation":[{"name":"Centrum Wiskunde and Informatica","place":["Amsterdam, The Netherlands"]},{"name":"Leiden University, Mathematical Institute","place":["Leiden, The Netherlands"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-4639-7660","authenticated-orcid":false,"given":"Johanna","family":"Loyer","sequence":"additional","affiliation":[{"name":"Inria","place":["Saclay, France"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2025,10,6]]},"reference":[{"key":"ref1:kyber","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1109\/EuroSP.2018.00032","article-title":"CRYSTALS-Kyber: a CCA-secure module-lattice-based KEM","author":"Joppe Bos","year":"2018"},{"key":"ref2:dilithium","doi-asserted-by":"publisher","first-page":"238","DOI":"10.13154\/tches.v2018.i1.238-268","article-title":"Crystals-dilithium: A lattice-based digital signature\n  scheme","author":"L\u00e9o Ducas","year":"2018","journal-title":"IACR Transactions on Cryptographic Hardware and Embedded\n  Systems"},{"key":"ref3:falcon","first-page":"1","article-title":"Falcon: Fast-Fourier lattice-based compact signatures over\n  NTRU","volume":"36","author":"Pierre-Alain Fouque","year":"2018","journal-title":"Submission to the NIST\u2019s post-quantum cryptography\n  standardization process"},{"key":"ref4:SE94","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice basis reduction: Improved practical algorithms and\n  solving subset sum problems","volume":"66","author":"Claus-Peter Schnorr","year":"1994","journal-title":"Mathematical programming"},{"key":"ref5:LN14","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1112\/S1461157014000333","article-title":"Approximating the densest sublattice from Rankin\u2019s\n  inequality","volume":"17","author":"Jianwei Li","year":"2014","journal-title":"LMS Journal of Computation and Mathematics"},{"key":"ref6:Duc18","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-319-78381-9_5","article-title":"Shortest vector from lattice sieving: a few dimensions for\n  free","author":"L\u00e9o Ducas","year":"2018"},{"key":"ref7:Kim22","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/j.jnt.2022.03.013","article-title":"Mean value formulas on sublattices and flags of the random\n  lattice","volume":"241","author":"Seungki Kim","year":"2022","journal-title":"Journal of Number Theory"},{"key":"ref8:LLL82","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"AK Lenstra","year":"1982","journal-title":"Math. ann"},{"key":"ref9:Che09","volume-title":"Lattice reduction and concrete security of fully homomorphic\n  encryption (Ph. D. thesis)","author":"Yuanmi Chen","year":"2013"},{"key":"ref10:Sod11","doi-asserted-by":"publisher","first-page":"945","DOI":"10.1007\/s00209-010-0772-8","article-title":"On the Poisson distribution of lengths of lattice vectors in\n  a random lattice","volume":"269","author":"Anders S\u00f6dergren","year":"2011","journal-title":"Mathematische Zeitschrift"},{"key":"ref11:Sch87","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","article-title":"A hierarchy of polynomial time lattice basis reduction\n  algorithms","volume":"53","author":"Claus-Peter Schnorr","year":"1987","journal-title":"Theoretical computer science"},{"key":"ref12:HPS11","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/978-3-642-22792-9_25","article-title":"Analyzing blockwise lattice algorithms using dynamical\n  systems","author":"Guillaume Hanrot","year":"2011"},{"key":"ref13:AD21","series-title":"London Mathematical Society Lecture Note Series","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1017\/9781108854207.004","volume-title":"Computational Cryptography: Algorithmic Aspects of\n  Cryptology","author":"Martin Albrecht","year":"2021"},{"key":"ref14:GSA","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/3-540-36494-3_14","article-title":"Lattice reduction by random sampling and birthday methods","author":"Claus Peter Schnorr","year":"2003"},{"key":"ref15:BSW18","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-030-03326-2_13","article-title":"Measuring, simulating and exploiting the head concavity\n  phenomenon in BKZ","author":"Shi Bai","year":"2018"},{"key":"ref16:CN11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-25385-0_1","article-title":"BKZ 2.0: Better lattice security estimates","author":"Yuanmi Chen","year":"2011"},{"key":"ref17:GHGKN06","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/11818175_7","article-title":"Rankin\u2019s constant and blockwise lattice reduction","author":"Nicolas Gama","year":"2006"},{"key":"ref18:Thu98","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1307\/mmj\/1030132184","article-title":"Higher-dimensional analogs of Hermite's constant.","volume":"45","author":"Jeffrey Lin Thunder","year":"1998","journal-title":"Michigan Mathematical Journal"},{"key":"ref19:DM13","doi-asserted-by":"publisher","first-page":"1103","DOI":"10.1137\/1.9781611973105.79","article-title":"Algorithms for the densest sub-lattice problem","author":"Daniel Dadush","year":"2013"},{"key":"ref20:NV08","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1515\/JMC.2008.009","article-title":"Sieve algorithms for the shortest vector problem are\n  practical","volume":"2","author":"Phong Q Nguyen","year":"2008","journal-title":"Journal of Mathematical Cryptology"},{"key":"ref21:BDGL16","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1137\/1.9781611974331.ch2","article-title":"New directions in nearest neighbor searching with\n  applications to lattice sieving","author":"Anja Becker","year":"2016"},{"key":"ref22:HK17","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-662-54365-8_2","article-title":"Improved algorithms for the approximate k-list problem in\n  euclidean norm","author":"Gottfried Herold","year":"2017"},{"key":"ref23:Ran53","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1112\/jlms\/s1-28.3.309","article-title":"On positive definite quadratic forms","volume":"1","author":"Robert Alexander Rankin","year":"1953","journal-title":"Journal of the London Mathematical Society"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T20:22:46Z","timestamp":1759782166000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/3\/12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,6]]},"references-count":23,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,10,6]]}},"URL":"https:\/\/doi.org\/10.62056\/ae0fhsfg","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,6]]},"assertion":[{"value":"2025-07-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-3-7"}}