{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T02:04:04Z","timestamp":1773194644028,"version":"3.50.1"},"reference-count":106,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T00:00:00Z","timestamp":1772755200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"publisher","award":["62541315"],"award-info":[{"award-number":["62541315"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Shanghai Municipal Education Com- 629 mission","award":["2021-01-07-00-08-E00101"],"award-info":[{"award-number":["2021-01-07-00-08-E00101"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>The rapid advancement of quantum computing poses a severe threat to traditional public key cryptosystems. Lattice-based cryptography has emerged as a core candidate for post-quantum cryptography due to its presumed quantum resistance, robust security foundations, and functional versatility, with its concrete security relying on the computational hardness of lattice problems. Existing lattice-based cryptography surveys mainly focus on cryptosystem design, scheme comparisons, and post-quantum cryptography standardization progress, with only cursory coverage of classical lattice algorithms that underpin the concrete security of lattice-based cryptography. We present the first systematic survey of classical lattice algorithms, focusing on two core categories of algorithms for solving lattice problems: approximate algorithms and exact algorithms. The approximate algorithms cover mainstream lattice basis reduction methods such as Lenstra\u2013Lenstra\u2013Lov\u00e1sz (LLL), Block Korkine\u2013Zolotarev (BKZ), and General Sieve Kernel (G6K) algorithms, as well as alternative frameworks. The exact algorithms encompass dominant techniques like enumeration and sieving algorithms, along with alternative strategies. We systematically trace the evolutionary trajectory and inherent logical connections of various algorithms, clarify their core mechanisms, and identify promising future research directions. This survey not only serves as an introductory guide for beginners but also provides a valuable reference for seasoned researchers, facilitating the concrete security evaluation of lattice-based cryptosystems and the design of novel lattice algorithms.<\/jats:p>","DOI":"10.3390\/cryptography10020017","type":"journal-article","created":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T17:25:59Z","timestamp":1772817959000},"page":"17","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Survey on Classical Lattice Algorithms"],"prefix":"10.3390","volume":"10","author":[{"given":"Tongchen","family":"Shen","sequence":"first","affiliation":[{"name":"Software Engineering Institute, East China Normal University, Shanghai 200241, China"}]},{"given":"Xiangxue","family":"Li","sequence":"additional","affiliation":[{"name":"School of Cryptology, East China Normal University, Shanghai 200241, China"}]}],"member":"1968","published-online":{"date-parts":[[2026,3,6]]},"reference":[{"key":"ref_1","unstructured":"Shor, P.W. (1994, January 20\u201322). Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (SFCS), Santa Fe, NM, USA."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Grover, L.K. (1996, January 22\u201324). A Fast Quantum Mechanical Algorithm for Database Search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), Philadelphia, PA, USA.","DOI":"10.1145\/237814.237866"},{"key":"ref_3","unstructured":"(2026, January 01). Post-Quantum Cryptography: Selected Algorithms, Available online: https:\/\/csrc.nist.gov\/projects\/post-quantum-cryptography\/post-quantum-cryptography-standardization\/selected-algorithms."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Ajtai, M. (1998, January 23\u201326). The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions (Extended Abstract). Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, TX, USA.","DOI":"10.1145\/276698.276705"},{"key":"ref_5","first-page":"212","article-title":"Another NP-complete partition problem and the complexity of computing short vectors in a lattice","volume":"12","author":"Boas","year":"1981","journal-title":"Inf. Process. Lett."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3992","DOI":"10.1103\/PhysRevLett.81.3992","article-title":"Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems","volume":"81","author":"Abrams","year":"1998","journal-title":"Phys. Rev. Lett."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"3960","DOI":"10.1038\/s41598-021-83521-5","article-title":"Universal quantum simulation of single-qubit nonunitary operators using duality quantum algorithm","volume":"11","author":"Zheng","year":"2021","journal-title":"Sci. Rep."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Ajtai, M. (1996, January 22\u201324). Generating Hard Instances of Lattice Problems. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), Philadelphia, PA, USA.","DOI":"10.1145\/237814.237838"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Regev, O. (2005, January 22\u201324). On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), Baltimore, MD, USA.","DOI":"10.1145\/1060590.1060603"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Bos, J.W., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Schwabe, P., Seiler, G., and Stehl\u00e9, D. (2018, January 24\u201326). CRYSTALS\u2014Kyber: A CCA-Secure Module-Lattice-Based KEM. Proceedings of the 2018 IEEE European Symposium on Security and Privacy (EuroS&P 2018), London, UK.","DOI":"10.1109\/EuroSP.2018.00032"},{"key":"ref_11","unstructured":"Alkim, E., Ducas, L., P\u00f6ppelmann, T., and Schwabe, P. (2016, January 10\u201312). Post-quantum Key Exchange\u2014A New Hope. Proceedings of the 25th USENIX Security Symposium (USENIX Security 16), Austin, TX, USA."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"238","DOI":"10.46586\/tches.v2018.i1.238-268","article-title":"CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme","volume":"2018","author":"Ducas","year":"2018","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Gorbunov, S., Vaikuntanathan, V., and Wee, H. (2013, January 1\u20134). Attribute-Based Encryption for Circuits. Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), Palo Alto, CA, USA.","DOI":"10.1145\/2488608.2488677"},{"key":"ref_14","unstructured":"Chillotti, I., Gama, N., Georgieva, M., and Izabach\u00e8ne, M. (2017, January 3\u20137). Improving TFHE: Faster Packed Homomorphic Encryption. Proceedings of the 23rd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), Hong Kong SAR, China."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Kim, A., Kim, M., and Song, Y. (2017, January 3\u20137). Homomorphic Encryption for Arithmetic of Approximate Numbers. Proceedings of the 23rd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), Hong Kong SAR, China.","DOI":"10.1007\/978-3-319-70694-8_15"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1515\/jmc-2015-0016","article-title":"On the Concrete Hardness of Learning with Errors","volume":"9","author":"Albrecht","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Curtis, B.R., Deo, A., Davidson, A., Player, R., Postlethwaite, E.W., Virdia, F., and Wunderer, T. (2018, January 5\u20137). Estimate all the LWE, NTRU schemes!. Proceedings of the 16th International Conference on Security and Cryptography (SCN), Amalfi, Italy.","DOI":"10.1007\/978-3-319-98113-0_19"},{"key":"ref_18","unstructured":"Wenger, E., Saxena, E., Malhou, M., Thieu, E., and Lauter, K. (2024, January 20\u201323). Benchmarking Attacks on Learning with Errors. Proceedings of the 45th IEEE Symposium on Security and Privacy (S&P), San Francisco, CA, USA."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Peikert, C., and Regev, O. (June, January 30). On Ideal Lattices and Learning with Errors over Rings. Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2010), French Riviera, France.","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Peikert, C., and Pepin, Z. (2019, January 1\u20135). Algebraically Structured LWE, Revisited. Proceedings of the 17th International Conference on Theory of Cryptography (TCC 2019), Nuremberg, Germany.","DOI":"10.1007\/978-3-030-36030-6_1"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J. (2008). Post-Quantum Cryptography, Springer Nature.","DOI":"10.1007\/978-3-540-88702-7"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Carrier, K., Meyer-Hilfiger, C., Shen, Y., and Tillich, J.-P. (2025, January 17\u201321). Assessing the Impact of a Variant of MATZOV\u2019s Dual Attack on Kyber. Proceedings of the 45th Annual International Cryptology Conference (CRYPTO 2025), Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-032-01855-7_15"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Karenin, A., Kirshanova, E., May, A., and Nowakowski, J. (2025, January 8\u201312). Fast Slicer for Batch-CVP: Making Lattice Hybrid Attacks Practical. Proceedings of the 31st International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2025), Melbourne, VIC, Australia.","DOI":"10.1007\/978-981-95-5099-9_4"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring Polynomials with Rational Coefficients","volume":"261","author":"Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice basis reduction: Improved practical algorithms and solving subset sum problems","volume":"66","author":"Schnorr","year":"1994","journal-title":"Math. Program."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Chen, Y., and Nguyen, P.Q. (2011, January 4\u20138). BKZ 2.0: Better Lattice Security Estimates. Proceedings of the 19th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), Seoul, Republic of Korea.","DOI":"10.1007\/978-3-642-25385-0_1"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., and Stevens, M. (2019, January 19\u201323). The General Sieve Kernel and New Records in Lattice Reduction. Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt), Darmstadt, Germany.","DOI":"10.1007\/978-3-030-17656-3_25"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1287\/moor.12.3.415","article-title":"Minkowski\u2019s Convex Body Theorem and Integer Programming","volume":"12","author":"Kannan","year":"1987","journal-title":"Math. Oper. Res."},{"key":"ref_29","unstructured":"Gama, N., Nguyen, P.Q., and Regev, O. (June, January 30). Lattice Enumeration Using Extreme Pruning. Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), Nice, France."},{"key":"ref_30","unstructured":"Albrecht, M.R., and Nguyen, P.Q. (2017, January 23\u201327). Random Sampling Revisited: Lattice Enumeration with Discrete Pruning. Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), Paris, France."},{"key":"ref_31","unstructured":"Albrecht, M.R., Bai, S., Fouque, P.-A., Kirchner, P., Stehl\u00e9, D., and Wen, W. (2020, January 17\u201321). Faster Enumeration-Based Lattice Reduction: Root Hermite Factor Bounds in Time 20.207n. Proceedings of the 40th Annual International Cryptology Conference (CRYPTO), Santa Barbara, CA, USA."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Becker, A., Ducas, L., Gama, N., and Laarhoven, T. (2016, January 10\u201312). New directions in nearest neighbor searching with applications to lattice sieving. Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, VA, USA.","DOI":"10.1137\/1.9781611974331.ch2"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., and Sivakumar, D. (2001, January 13\u201315). A sieve algorithm for the shortest lattice vector problem. Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), Heraklion, Crete, Greece.","DOI":"10.1145\/380752.380857"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Micciancio, D., and Voulgaris, P. (2010, January 17\u201319). Faster Exponential Time Algorithms for the Shortest Vector Problem (SVP). Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Austin, TX, USA.","DOI":"10.1137\/1.9781611973075.119"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Micciancio, D., and Voulgaris, P. (2010, January 5\u20138). A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), Cambridge, MA, USA.","DOI":"10.1145\/1806689.1806739"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Dadush, D., and Bonifas, N. (2015, January 4\u20136). Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA.","DOI":"10.1137\/1.9781611973730.22"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1515\/jmc-2020-0074","article-title":"Approximate Voronoi Cells for Lattices, Revisited","volume":"15","author":"Laarhoven","year":"2021","journal-title":"J. Math. Cryptol."},{"key":"ref_38","unstructured":"Aggarwal, D., Dadush, D., Regev, O., and Stephens-Davidowitz, N. (2015, January 14\u201317). Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling: Extended Abstract. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2015), Portland, OR, USA."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Dadush, D., and Stephens-Davidowitz, N. (2015, January 17\u201320). Solving the Closest Vector Problem in 2n Time\u2014The Discrete Gaussian Strikes Again!. Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2015.41"},{"key":"ref_40","first-page":"53","article-title":"A survey on lattice-based cryptography","volume":"29","author":"Simion","year":"2012","journal-title":"Acta Univ. Apulensis Math.-Inform."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Dam, D.-T., Tran, T.-H., Hoang, V.-P., Pham, C.-K., and Hoang, T.-T. (2023). A survey of post-quantum cryptography: Start of a new race. Cryptography, 7.","DOI":"10.3390\/cryptography7030040"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1186\/s42400-023-00198-1","article-title":"A survey on lattice-based digital signature","volume":"7","author":"Liu","year":"2024","journal-title":"Cybersecurity"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1049\/ise2.12101","article-title":"Lattice-based cryptosystems in standardisation processes: A survey","volume":"17","author":"Wang","year":"2023","journal-title":"IET Inf. Secur."},{"key":"ref_44","first-page":"281","article-title":"Lattice-based cryptography in the quantum era: A survey","volume":"2023","author":"Cisneros","year":"2023","journal-title":"Interfaces"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1007\/s11401-023-0053-6","article-title":"Lattice-based cryptography: A survey","volume":"44","author":"Wang","year":"2023","journal-title":"Chin. Ann. Math. B"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Gheorghiu, V., Postlethwaite, E.W., and Schanck, J.M. (2020, January 7\u201311). Estimating Quantum Speedups for Lattice Sieves. Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2020), Daejeon, Republic of Korea.","DOI":"10.1007\/978-3-030-64834-3_20"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Cramer, R., Ducas, L., Peikert, C., and Regev, O. (2016, January 8\u201312). Recovering Short Generators of Principal Ideals in Cyclotomic Rings. Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016), Vienna, Austria.","DOI":"10.1007\/978-3-662-49896-5_20"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/3431725","article-title":"Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time","volume":"68","author":"Cramer","year":"2021","journal-title":"J. ACM"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Lee, C., Pellet-Mary, A., Stehl\u00e9, D., and Wallet, A. (2019, January 8\u201312). An LLL Algorithm for Module Lattices. Proceedings of the 25th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2019), Kobe, Japan.","DOI":"10.1007\/978-3-030-34621-8_3"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Mukherjee, T., and Stephens-Davidowitz, N. (2020, January 17\u201321). Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP. Proceedings of the 40th Annual International Cryptology Conference (CRYPTO 2020), Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-030-56880-1_8"},{"key":"ref_51","unstructured":"Arora, S., and Ge, R. (2011, January 4\u20138). New Algorithms for Learning in Presence of Errors. Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Zurich, Switzerland."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Steiner, M.J. (2024, January 26\u201330). The Complexity of Algebraic Algorithms for LWE. Proceedings of the 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2024), Zurich, Switzerland.","DOI":"10.1007\/978-3-031-58734-4_13"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s10623-013-9864-x","article-title":"On the complexity of the BKW algorithm on LWE","volume":"74","author":"Albrecht","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Jager, T., and Pan, J. Memory-Efficient BKW Algorithm for Solving the LWE Problem. Proceedings of the 28th IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2025), R\u00f8ros, Norway, 12\u201315 May 2025, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-031-91823-0"},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Lovasz, L. (1986). An Algorithmic Theory of Numbers, Graphs and Convexity, SIAM Publications. CBMS-NSF Regional Conference Series in Applied Mathematics.","DOI":"10.1137\/1.9781611970203"},{"key":"ref_56","unstructured":"Gama, N., and Nguyen, P.Q. (2008, January 13\u201317). Predicting Lattice Reduction. Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2008), Istanbul, Turkey."},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"Bai, S., Stehl\u00e9, D., and Wen, W. (2018, January 2\u20136). Measuring, Simulating and Exploiting the Head Concavity Phenomenon in BKZ. Proceedings of the 24th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2018), Brisbane, QLD, Australia.","DOI":"10.1007\/978-3-030-03326-2_13"},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0747-7171(87)80061-5","article-title":"A Modification of the LLL Reduction Algorithm","volume":"4","author":"Pohst","year":"1987","journal-title":"J. Symb. Comput."},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/2455.2461","article-title":"Solving Low-Density Subset Sum Problems","volume":"32","author":"Lagarias","year":"1985","journal-title":"J. ACM"},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/s001459900030","article-title":"Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities","volume":"10","author":"Coppersmith","year":"1997","journal-title":"J. Cryptol."},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1137\/070705702","article-title":"An LLL Algorithm with Quadratic Complexity","volume":"39","author":"Nguyen","year":"2009","journal-title":"SIAM J. Comput."},{"key":"ref_62","unstructured":"(2026, January 01). fplll. Available online: https:\/\/github.com\/fplll\/fplll."},{"key":"ref_63","doi-asserted-by":"crossref","unstructured":"Ducas, L., Pulles, L.N., and Stevens, M. (2025, January 8\u201312). Towards a Modern LLL Implementation. Proceedings of the 31st International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2025), Melbourne, VIC, Australia.","DOI":"10.1007\/978-981-95-5099-9_3"},{"key":"ref_64","doi-asserted-by":"crossref","unstructured":"Neumaier, A., and Stehl\u00e9, D. (2016, January 19\u201322). Faster LLL-type Reduction of Lattice Bases. Proceedings of the ACM International Symposium on Symbolic and Algebraic Computation (ISSAC 2016), Waterloo, ON, Canada.","DOI":"10.1145\/2930889.2930917"},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BF01202355","article-title":"Simultaneous reduction of a lattice basis and its reciprocal basis","volume":"13","author":"Seysen","year":"1993","journal-title":"Combinatorica"},{"key":"ref_66","doi-asserted-by":"crossref","unstructured":"Kirchner, P., Espitau, T., and Fouque, P.-A. (2021, January 16\u201320). Towards Faster Polynomial-Time Lattice Reduction. Proceedings of the 41st Annual International Cryptology Conference (CRYPTO 2021), Virtual Event.","DOI":"10.1007\/978-3-030-84245-1_26"},{"key":"ref_67","doi-asserted-by":"crossref","unstructured":"Aono, Y., Wang, Y., Hayashi, T., and Takagi, T. (2016, January 8\u201312). Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator. Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016), Vienna, Austria.","DOI":"10.1007\/978-3-662-49890-3_30"},{"key":"ref_68","doi-asserted-by":"crossref","unstructured":"Schnorr, C.-P. (March, January 27). Lattice Reduction by Random Sampling and Birthday Methods. Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003), Berlin\/Heidelberg, Germany.","DOI":"10.1007\/3-540-36494-3_14"},{"key":"ref_69","doi-asserted-by":"crossref","unstructured":"Yu, Y., and Ducas, L. (2017, January 16\u201318). Second Order Statistical Behavior of LLL and BKZ. Proceedings of the 24th International Conference on Selected Areas in Cryptography (SAC 2017), Ottawa, ON, Canada.","DOI":"10.1007\/978-3-319-72565-9_1"},{"key":"ref_70","unstructured":"Chen, Y. (2013). R\u00e9duction de R\u00e9seau et S\u00e9curit\u00e9 Concr\u00e8te du Chiffrement Compl\u00e8tement Homomorphe. [Ph.D. Thesis, Paris 7]."},{"key":"ref_71","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Bai, S., Li, J., and Rowell, J. (2021, January 16\u201320). Lattice Reduction with Approximate Enumeration Oracles\u2014Practical Algorithms and Concrete Performance. Proceedings of the 41st Annual International Cryptology Conference (CRYPTO 2021), Virtual Event.","DOI":"10.1007\/978-3-030-84245-1_25"},{"key":"ref_72","doi-asserted-by":"crossref","unstructured":"Laarhoven, T. (2015, January 16\u201320). Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing. Proceedings of the 45th Annual International Cryptology Conference (CRYPTO), Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-662-47989-6_1"},{"key":"ref_73","unstructured":"Ducas, L. (May, January 29). Shortest Vector from Lattice Sieving: A Few Dimensions for Free. Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt), Tel Aviv, Israel."},{"key":"ref_74","doi-asserted-by":"crossref","unstructured":"Laarhoven, T., and Mariano, A. (2018, January 15\u201317). Progressive lattice sieving. Proceedings of the 11th International Workshop on Post-Quantum Cryptography (PQC), Minneapolis, MN, USA.","DOI":"10.1007\/978-3-319-79063-3_14"},{"key":"ref_75","doi-asserted-by":"crossref","unstructured":"Ducas, L., Stevens, M., and van Woerden, W.P.J. (2021, January 17\u201321). Advanced Lattice Sieving on GPUs, with Tensor Cores. Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2021), Zagreb, Croatia.","DOI":"10.1007\/978-3-030-77886-6_9"},{"key":"ref_76","doi-asserted-by":"crossref","unstructured":"Gama, N., and Nguyen, P.Q. (2008, January 17\u201320). Finding Short Lattice Vectors Within Mordell\u2019s Inequality. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC 2008), Victoria, BC, Canada.","DOI":"10.1145\/1374376.1374408"},{"key":"ref_77","doi-asserted-by":"crossref","unstructured":"Micciancio, D., and Walter, M. (2016, January 8\u201312). Practical, Predictable Lattice Basis Reduction. Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016), Vienna, Austria.","DOI":"10.1007\/978-3-662-49890-3_31"},{"key":"ref_78","doi-asserted-by":"crossref","unstructured":"Buchmann, J., and Ludwig, C. (2006, January 23\u201328). Practical Lattice Basis Sampling Reduction. Proceedings of the 7th International Symposium on Algorithmic Number Theory (ANTS-VII), Berlin\/Heidelberg, Germany.","DOI":"10.1007\/11792086_17"},{"key":"ref_79","first-page":"67","article-title":"An Accelerated Algorithm for Solving SVP Based on Statistical Analysis","volume":"23","author":"Fukase","year":"2015","journal-title":"J. Inf. Process."},{"key":"ref_80","doi-asserted-by":"crossref","unstructured":"Teruya, T., Kashiwabara, K., and Hanaoka, G. (2018, January 25\u201329). Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem. Proceedings of the 21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018), Rio de Janeiro, Brazil.","DOI":"10.1007\/978-3-319-76578-5_15"},{"key":"ref_81","doi-asserted-by":"crossref","unstructured":"Hanrot, G., Pujol, X., and Stehl\u00e9, D. (2011, January 14\u201318). Analyzing Blockwise Lattice Algorithms Using Dynamical Systems. Proceedings of the 31st Annual Cryptology Conference (CRYPTO 2011), Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-642-22792-9_25"},{"key":"ref_82","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1007\/s00145-024-09527-0","article-title":"A Complete Analysis of the BKZ Lattice Reduction Algorithm","volume":"38","author":"Li","year":"2025","journal-title":"J. Cryptol."},{"key":"ref_83","doi-asserted-by":"crossref","unstructured":"Fincke, U., and Pohst, M. (1983, January 28\u201330). A Procedure for Determining Algebraic Integers of Given Norm. Proceedings of the European Computer Algebra Conference (EUROCAL \u201983), London, UK.","DOI":"10.1007\/3-540-12868-9_103"},{"key":"ref_84","unstructured":"Hanrot, G., and Stehl\u00e9, D. (2007, January 19\u201323). Improved Analysis of Kannan\u2019s Shortest Lattice Vector Algorithm. Proceedings of the 27th Annual International Cryptology Conference (CRYPTO 2007), Santa Barbara, CA, USA."},{"key":"ref_85","doi-asserted-by":"crossref","unstructured":"Nguyen, P.Q., and Vall\u00e9e, B. (2010). The LLL Algorithm\u2014Survey and Applications, Springer. Information Security and Cryptography.","DOI":"10.1007\/978-3-642-02295-1"},{"key":"ref_86","doi-asserted-by":"crossref","unstructured":"Schnorr, C.-P., and H\u00f6rner, H.H. (1995, January 21\u201325). Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction. Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT \u201995), Saint-Malo, France.","DOI":"10.1007\/3-540-49264-X_1"},{"key":"ref_87","doi-asserted-by":"crossref","unstructured":"Aono, Y., Nguyen, P.Q., and Shen, Y. (2018, January 2\u20136). Quantum Lattice Enumeration and Tweaking Discrete Pruning. Proceedings of the 24th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2018), Brisbane, QLD, Australia.","DOI":"10.1007\/978-3-030-03326-2_14"},{"key":"ref_88","unstructured":"Chen, Y., Chen, Z., Guo, T., Sun, C., Wen, W.-Q., and Yu, Y. (2025). Time-Memory Trade-off for Enumeration. IACR Cryptol. ePrint Arch., 2227, Available online: https:\/\/eprint.iacr.org\/2025\/2227."},{"key":"ref_89","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1515\/JMC.2008.009","article-title":"Sieve Algorithms for the Shortest Vector Problem (SVP) are Practical","volume":"2","author":"Nguyen","year":"2008","journal-title":"J. Math. Crypt."},{"key":"ref_90","doi-asserted-by":"crossref","unstructured":"Wang, X., Liu, M., Tian, C., and Bi, J. (2011, January 10\u201313). Improved Nguyen-Vidick Heuristic Sieve Algorithm for the Shortest Vector Problem. Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security (AsiaCCS), Hong Kong SAR, China.","DOI":"10.1145\/1966913.1966915"},{"key":"ref_91","unstructured":"Zhang, F., Pan, Y., and Hu, G. (2013, January 14\u201316). A Three-Level Sieve Algorithm for the Shortest Vector Problem. Proceedings of the 21st International Conference on Selected Areas in Cryptography (SAC), Montreal, QC, Canada."},{"key":"ref_92","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1112\/S1461157016000292","article-title":"Tuple lattice sieving","volume":"19","author":"Bai","year":"2016","journal-title":"LMS J. Comput. Math."},{"key":"ref_93","doi-asserted-by":"crossref","unstructured":"Herold, G., and Kirshanova, E. (2017, January 20\u201323). Improved Algorithms for the Approximate k-List Problem in Euclidean Norm. Proceedings of the 20th IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC), Yokohama, Japan.","DOI":"10.1007\/978-3-662-54365-8_2"},{"key":"ref_94","unstructured":"Herold, G., Kirshanova, E., and Laarhoven, T. (May, January 29). Speed-Ups and Time\u2013Memory Trade-Offs for Tuple Lattice Sieving. Proceedings of the 21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC), Jerusalem, Israel."},{"key":"ref_95","unstructured":"Laarhoven, T. (2015). Search Problems in Cryptography: From Fingerprinting to Lattice Sieving. [Ph.D. Thesis, Eindhoven University of Technology]."},{"key":"ref_96","unstructured":"Becker, A., Gama, N., and Joux, A. (2014, January 11\u201315). Solving shortest and closest vector problems: The decomposition approach. Proceedings of the 11th Algorithmic Number Theory Symposium (ANTS), Pohang, Republic of Korea."},{"key":"ref_97","doi-asserted-by":"crossref","unstructured":"Kirshanova, E., and Laarhoven, T. (2021, January 16\u201320). Lower Bounds on Lattice Sieving and Information Set Decoding. Proceedings of the 41st Annual International Cryptology Conference (CRYPTO), Virtual Event.","DOI":"10.1007\/978-3-030-84245-1_27"},{"key":"ref_98","doi-asserted-by":"crossref","unstructured":"Shen, T., Li, X., and Wang, L. (2026). Lower Bound on the Overlattice-Based Sieve Algorithm. Cryptography, 10.","DOI":"10.3390\/cryptography10010005"},{"key":"ref_99","unstructured":"Zhao, Z., Ding, J., and Yang, B.-Y. (2024). BGJ15 Revisited: Sieving with Streamed Memory Access. IACR Cryptol. ePrint Arch., 739, Available online: https:\/\/eprint.iacr.org\/2024\/739."},{"key":"ref_100","unstructured":"Becker, A., Gama, N., and Joux, A. (2015). Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest search. IACR Cryptol. ePrint Arch., 102, Available online: https:\/\/eprint.iacr.org\/2015\/522."},{"key":"ref_101","unstructured":"(2026, January 01). SVP Challenge. Available online: https:\/\/www.latticechallenge.org\/svp-challenge\/."},{"key":"ref_102","unstructured":"Micciancio, D., and Regev, O. (2004, January 17\u201319). Worst-Case to Average-Case Reductions Based on Gaussian Measures. Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), Rome, Italy."},{"key":"ref_103","doi-asserted-by":"crossref","first-page":"1212","DOI":"10.1109\/18.915688","article-title":"The Hardness of the Closest Vector Problem with Preprocessing","volume":"47","author":"Micciancio","year":"2001","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_104","doi-asserted-by":"crossref","first-page":"2201","DOI":"10.1109\/TIT.2002.800499","article-title":"Closest Point Search in Lattices","volume":"48","author":"Agrell","year":"2002","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_105","doi-asserted-by":"crossref","unstructured":"Doulgerakis, E., Laarhoven, T., and de Weger, B. (2019, January 8\u201310). Finding Closest Lattice Vectors Using Approximate Voronoi Cells. Proceedings of the 10th International Conference on Post-Quantum Cryptography (PQCrypto 2019), Chongqing, China.","DOI":"10.1007\/978-3-030-25510-7_1"},{"key":"ref_106","doi-asserted-by":"crossref","unstructured":"Ducas, L., Laarhoven, T., and van Woerden, W.P.J. (2020, January 4\u20137). The Randomized Slicer for CVPP: Sharper, Faster, Smaller, Batchier. Proceedings of the 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2020), Edinburgh, UK.","DOI":"10.1007\/978-3-030-45388-6_1"}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/10\/2\/17\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T05:27:56Z","timestamp":1773120476000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/10\/2\/17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,6]]},"references-count":106,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2026,4]]}},"alternative-id":["cryptography10020017"],"URL":"https:\/\/doi.org\/10.3390\/cryptography10020017","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,6]]}}}