{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T14:57:42Z","timestamp":1773154662229,"version":"3.50.1"},"reference-count":35,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":"crossref","award":["62272040"],"award-info":[{"award-number":["62272040"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003399","name":"Science and Technology Commission of Shanghai Municipality","doi-asserted-by":"publisher","award":["23511100200"],"award-info":[{"award-number":["23511100200"]}],"id":[{"id":"10.13039\/501100003399","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003395","name":"Shanghai Municipal Education Commission","doi-asserted-by":"crossref","award":["2021-01-07-00-08-E00101"],"award-info":[{"award-number":["2021-01-07-00-08-E00101"]}],"id":[{"id":"10.13039\/501100003395","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>Lattice-based cryptography stands as one of the most pivotal candidates in post-quantum cryptography. To configure the parameters of lattice-based cryptographic schemes, a thorough comprehension of their concrete security is indispensable. Lattice sieving algorithms represent among the most critical tools for conducting concrete security analysis. Currently, the state-of-the-art BDGL-sieve (SODA 2016) achieves a time complexity of 20.292n+o(n), and Kirshanova and Laarhoven (CRYPTO 2021) have proven that the BDGL-sieve attains the lower bound under the technical paradigm of the Nearest Neighbor Search (NNS) problem. A natural question emerges: whether overlattice-based sieving algorithms (ANTS 2014) can outperform the BDGL-sieve within an alternative technical framework. This work provides an almost negative response to this question. Specifically, we propose a generalized overlattice tower model, which facilitates the proof of the lower bound for the overlattice-based method. Our findings indicate that the original Overlattice-sieve has already reached this lower bound. Consequently, the BDGL-sieve will maintain its status as the sieving algorithm with optimal time complexity, unless a revolutionary technical optimization is developed in the future.<\/jats:p>","DOI":"10.3390\/cryptography10010005","type":"journal-article","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T12:23:44Z","timestamp":1767356624000},"page":"5","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bound on the Overlattice-Based Sieve Algorithm"],"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":"Software Engineering Institute, East China Normal University, Shanghai 200241, China"}]},{"given":"Licheng","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Cyberspace Science and Technology, Beijing Institute of Technology, Beijing 100081, China"}]}],"member":"1968","published-online":{"date-parts":[[2026,1,1]]},"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":"(2025, December 26). 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. (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_5","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_6","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., and Vaikuntanathan, V. (2008, January 17\u201320). How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), Victoria, BC, Canada.","DOI":"10.1145\/1374376.1374407"},{"key":"ref_7","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_8","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, China."},{"key":"ref_9","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, China.","DOI":"10.1007\/978-3-319-70694-8_15"},{"key":"ref_10","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. Crypto."},{"key":"ref_11","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_12","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_13","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_14","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_15","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_16","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_17","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_18","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_19","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, Greece.","DOI":"10.1145\/380752.380857"},{"key":"ref_20","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_21","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, China.","DOI":"10.1145\/1966913.1966915"},{"key":"ref_22","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_23","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_24","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_25","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., Available online: https:\/\/eprint.iacr.org\/2015\/522."},{"key":"ref_26","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_27","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_28","unstructured":"Laarhoven, T. (2015). Search Problems in Cryptography: From Fingerprinting to Lattice Sieving. [Ph.D. Thesis, Eindhoven University of Technology]."},{"key":"ref_29","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_30","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_31","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_32","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_33","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_34","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_35","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"}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/10\/1\/5\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T05:12:51Z","timestamp":1767676371000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/10\/1\/5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,1]]},"references-count":35,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,2]]}},"alternative-id":["cryptography10010005"],"URL":"https:\/\/doi.org\/10.3390\/cryptography10010005","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,1]]}}}