{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:37:47Z","timestamp":1760236667220,"version":"build-2065373602"},"reference-count":68,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2021,12,13]],"date-time":"2021-12-13T00:00:00Z","timestamp":1639353600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this work, we give provable sieving algorithms for the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on lattices in \u2113p norm (1\u2264p\u2264\u221e). The running time we obtain is better than existing provable sieving algorithms. We give a new linear sieving procedure that works for all \u2113p norm (1\u2264p\u2264\u221e). The main idea is to divide the space into hypercubes such that each vector can be mapped efficiently to a sub-region. We achieve a time complexity of 22.751n+o(n), which is much less than the 23.849n+o(n) complexity of the previous best algorithm. We also introduce a mixed sieving procedure, where a point is mapped to a hypercube within a ball and then a quadratic sieve is performed within each hypercube. This improves the running time, especially in the \u21132 norm, where we achieve a time complexity of 22.25n+o(n), while the List Sieve Birthday algorithm has a running time of 22.465n+o(n). We adopt our sieving techniques to approximation algorithms for SVP and CVP in \u2113p norm (1\u2264p\u2264\u221e) and show that our algorithm has a running time of 22.001n+o(n), while previous algorithms have a time complexity of 23.169n+o(n).<\/jats:p>","DOI":"10.3390\/a14120362","type":"journal-article","created":{"date-parts":[[2021,12,14]],"date-time":"2021-12-14T01:20:41Z","timestamp":1639444841000},"page":"362","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Faster Provable Sieving Algorithms for the Shortest Vector Problem and the Closest Vector Problem on Lattices in \u2113p Norm"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6463-9100","authenticated-orcid":false,"given":"Priyanka","family":"Mukhopadhyay","sequence":"first","affiliation":[{"name":"Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON N2L 3G1, Canada"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,13]]},"reference":[{"key":"ref_1","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_2","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","article-title":"Integer programming with a fixed number of variables","volume":"8","author":"Lenstra","year":"1983","journal-title":"Math. Oper. Res."},{"key":"ref_3","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_4","doi-asserted-by":"crossref","unstructured":"Dadush, D., Peikert, C., and Vempala, S. (2011, January 22\u201325). Enumerative lattice algorithms in any norm via m-ellipsoid coverings. Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, CA, USA.","DOI":"10.1109\/FOCS.2011.31"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., H\u00e4hnle, N., and Niemeier, M. (2011, January 13\u201315). Covering cubes and the closest vector problem. Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, Paris, France.","DOI":"10.1145\/1998196.1998264"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1090\/psapm\/042\/1095552","article-title":"The rise and fall of knapsack cryptosystems","volume":"42","author":"Odlyzko","year":"1990","journal-title":"Cryptol. Comput. Number Theory"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s001459900042","article-title":"Lattice reduction: A toolbox for the cryptanalyst","volume":"11","author":"Joux","year":"1998","journal-title":"J. Cryptol."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Nguyen, P.Q., and Stern, J. (2001). The two faces of lattices in cryptology. Cryptography and Lattices, Springer.","DOI":"10.1007\/3-540-44670-2_12"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Landau, S., and Miller, G.L. (1983). Solvability by radicals is in polynomial time. Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, ACM.","DOI":"10.1145\/800061.808743"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01201999","article-title":"Improved low-density subset sum algorithms","volume":"2","author":"Coster","year":"1992","journal-title":"Comput. Complex."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ajtai, M. (1996, January 22\u201324). Generating hard instances of lattice problems. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA.","DOI":"10.1145\/237814.237838"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1137\/S0097539705447360","article-title":"Worst-case to average-case reductions based on Gaussian measures","volume":"37","author":"Micciancio","year":"2007","journal-title":"SIAM J. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Gentry, C. (June, January 31). Fully homomorphic encryption using ideal lattices. Proceedings of the STOC\u201909\u2014Proceedings of the 2009 ACM International Symposium on Theory of Computing, Bethesda, MD, USA.","DOI":"10.1145\/1536414.1536440"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/1568318.1568324","article-title":"On lattices, learning with errors, random linear codes, and cryptography","volume":"56","author":"Regev","year":"2009","journal-title":"J. ACM"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., and Vaikuntanathan, V. (2011, January 23\u201325). Efficient fully homomorphic encryption from (standard) LWE. Proceedings of the FOCS, Palm Springs, CA, USA.","DOI":"10.1109\/FOCS.2011.12"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Langlois, A., Peikert, C., Regev, O., and Stehl\u00e9, D. (2013, January 1\u20134). Classical hardness of learning with errors. Proceedings of the STOC, Palo Alto, CA, USA.","DOI":"10.1145\/2488608.2488680"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., and Vaikuntanathan, V. (2014, January 12\u201314). Lattice-based FHE as secure as PKE. Proceedings of the ITCS, Princeton, NJ, USA.","DOI":"10.1145\/2554797.2554799"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1561\/0400000074","article-title":"A decade of lattice cryptography","volume":"10","author":"Peikert","year":"2016","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"ref_19","unstructured":"Ducas, L., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., and Stehl\u00e9, D. (2021, December 08). Crystals\u2013Dilithium: Digital Signatures from Module Lattices. IACR Transactions on Symmetric Cryptology. Available online: https:\/\/repository.ubn.ru.nl\/bitstream\/handle\/2066\/191703\/191703.pdf."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Dadush, D., Regev, O., and Stephens-Davidowitz, N. (2015, January 14\u201317). Solving the Shortest Vector Problem in 2n time via Discrete Gaussian sampling. Proceedings of the STOC, Portland, OR, USA.","DOI":"10.1109\/FOCS.2015.41"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., and Sivakumar, D. (2001, January 6\u20138). A sieve algorithm for the shortest lattice vector problem. Proceedings of the STOC, Heraklion, Greece.","DOI":"10.1145\/380752.380857"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1090\/S0025-5718-1985-0777278-8","article-title":"Improved methods for calculating vectors of short length in a lattice, including a complexity analysis","volume":"44","author":"Fincke","year":"1985","journal-title":"Math. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","article-title":"A hierarchy of polynomial time lattice basis reduction algorithms","volume":"53","author":"Schnorr","year":"1987","journal-title":"Theor. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/100811970","article-title":"A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations","volume":"42","author":"Micciancio","year":"2013","journal-title":"SIAM J. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"19237","DOI":"10.1073\/pnas.1203863110","article-title":"Near-optimal deterministic algorithms for volume computation via m-ellipsoids","volume":"110","author":"Dadush","year":"2013","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Hanrot, G., Pujol, X., and Stehl\u00e9, D. (2011). Algorithms for the shortest and closest lattice vector problems. International Conference on Coding and Cryptology, Springer.","DOI":"10.1007\/978-3-642-20901-7_10"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Micciancio, D., and Voulgaris, P. (2010, January 17\u201319). Faster exponential time algorithms for the shortest vector problem. Proceedings of the SODA, Austin, TX, USA.","DOI":"10.1137\/1.9781611973075.119"},{"key":"ref_28","first-page":"605","article-title":"Solving the shortest lattice vector problem in time 22.465n","volume":"2009","author":"Pujol","year":"2009","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_29","unstructured":"Aggarwal, D., and Stephens-Davidowitz, N. (2017). Just take the average! an embarrassingly simple 2n-time algorithm for SVP (and CVP). arXiv."},{"key":"ref_30","first-page":"139","article-title":"Shortest lattice vectors in the presence of gaps","volume":"2011","author":"Liu","year":"2011","journal-title":"IACR Cryptol. Eprint Arch."},{"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 are practical","volume":"2","author":"Nguyen","year":"2008","journal-title":"J. Math. Cryptol."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Wang, X., Liu, M., Tian, C., and Bi, J. (2011, January 22\u201324). Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem. Proceedings of the AsiaCCS, Hong Kong, China.","DOI":"10.1145\/1966913.1966915"},{"key":"ref_33","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 Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, USA.","DOI":"10.1137\/1.9781611974331.ch2"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Laarhoven, T., and de Weger, B. (2015). Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing. International Conference on Cryptology and Information Security in Latin America, Springer.","DOI":"10.1007\/978-3-319-22174-8_6"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Becker, A., and Laarhoven, T. (2016). Efficient (ideal) lattice sieving using cross-polytope LSH. International Conference on Cryptology in Africa, Springer.","DOI":"10.1007\/978-3-319-31517-1_1"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Herold, G., and Kirshanova, E. (2017). Improved algorithms for the approximate k-list problem in Euclidean norm. IACR International Workshop on Public Key Cryptography, Springer.","DOI":"10.1007\/978-3-662-54365-8_2"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Herold, G., Kirshanova, E., and Laarhoven, T. (2018). Speed-ups and time\u2013memory trade-offs for tuple lattice sieving. IACR International Workshop on Public Key Cryptography, Springer.","DOI":"10.1007\/978-3-319-76578-5_14"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Laarhoven, T., and Mariano, A. (2018). Progressive lattice sieving. International Conference on Post-Quantum Cryptography, Springer.","DOI":"10.1007\/978-3-319-79063-3_14"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Mariano, A., and Bischof, C. (2016, January 17\u201319). Enhancing the scalability and memory usage of hash sieve on multi-core CPUs. Proceedings of the 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), Heraklion, Greece.","DOI":"10.1109\/PDP.2016.31"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Mariano, A., Laarhoven, T., and Bischof, C. (2017, January 6\u20138). A parallel variant of LD sieve for the SVP on lattices. Proceedings of the 2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP), St. Petersburg, Russia.","DOI":"10.1109\/PDP.2017.60"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Yang, S.-Y., Kuo, P.-C., Yang, B.-Y., and Cheng, C.-M. (2017). Gauss sieve algorithm on GPUs. Cryptographers\u2019 Track at the RSA Conference, Springer.","DOI":"10.1007\/978-3-319-52153-4_3"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Ducas, L. (2018). Shortest vector from lattice sieving: A few dimensions for free. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-319-78381-9_5"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., and Stevens, M. (2019). The general sieve kernel and new records in lattice reduction. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-030-17656-3_25"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0020-0190(99)00083-6","article-title":"Approximating shortest lattice vectors is not harder than approximating closest lattice vectors","volume":"71","author":"Goldreich","year":"1999","journal-title":"Inf. Process. Lett."},{"key":"ref_45","unstructured":"Ajtai, M., Kumar, R., and Sivakumar, D. (2002, January 15\u201320). Sampling short lattice vectors and the closest lattice vector problem. Proceedings of the CCC, Beijing, China."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Dadush, D., and Stephens-Davidowitz, N. (2015, January 18\u201320). Solving the closest vector problem in 2n time\u2013the Discrete Gaussian strikes again!. Proceedings of the Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium, Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2015.41"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1648","DOI":"10.1016\/j.tcs.2008.12.045","article-title":"Sampling methods for shortest vectors, closest vectors and successive minima","volume":"410","author":"Naewe","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_48","unstructured":"Arvind, V., and Joglekar, P.S. (2008). Some sieving algorithms for lattice problems. LIPIcs-Leibniz International Proceedings in Informatics, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"ref_49","unstructured":"Aggarwal, D., and Mukhopadhyay, P. (2018). Improved algorithms for the shortest vector problem and the closest vector problem in the infinity norm. arXiv."},{"key":"ref_50","unstructured":"van Emde Boas, P. (1981). Another NP-Complete Partition Problem and the Complexity of Computing Short Vectors in a Lattice, Department of Mathematics, University of Amsterdam. Technical Report."},{"key":"ref_51","unstructured":"Ajtai, M. (1998, January 24\u201326). The shortest vector problem in \u21132 is NP-hard for randomized reductions. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, Dallas, TX, USA."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"2008","DOI":"10.1137\/S0097539700373039","article-title":"The shortest vector problem is NP-hard to approximate to within some constant","volume":"30","author":"Micciancio","year":"2001","journal-title":"SIAM J. Comput."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s00493-003-0019-y","article-title":"Approximating CVP to within almost-polynomial factors is NP-hard","volume":"23","author":"Dinur","year":"2003","journal-title":"Combinatorica"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Dinur, I. (2000). Approximating SVP\u221e to within almost-polynomial factors is NP-hard. Italian Conference on Algorithms and Complexity, Springer.","DOI":"10.1007\/3-540-46521-9_22"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/j.jcss.2021.09.002","article-title":"The projection games conjecture and the hardness of approximation of SSAT and related problems","volume":"123","author":"Mukhopadhyay","year":"2021","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"221","DOI":"10.4086\/toc.2015.v011a007","article-title":"The projection games conjecture and the NP-hardness of ln n-approximating Set-Cover","volume":"11","author":"Moshkovitz","year":"2015","journal-title":"Theory Comput."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1145\/1089023.1089027","article-title":"Hardness of approximating the shortest vector problem in lattices","volume":"52","author":"Khot","year":"2005","journal-title":"J. ACM"},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"513","DOI":"10.4086\/toc.2012.v008a023","article-title":"Tensor-based hardness of the shortest vector problem to within almost polynomial factors","volume":"8","author":"Haviv","year":"2012","journal-title":"Theory Comput."},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Bennett, H., Golovnev, A., and Stephens-Davidowitz, N. (2017). On the quantitative hardness of CVP. arXiv.","DOI":"10.1109\/FOCS.2017.11"},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., and Stephens-Davidowitz, N. (2018, January 25\u201329). (gap\/S)ETH hardness of SVP. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, USA.","DOI":"10.1145\/3188745.3188840"},{"key":"ref_61","doi-asserted-by":"crossref","unstructured":"Dadush, D., and Kun, G. (2013, January 6\u20138). Lattice sparsification and the approximate closest vector problem. Proceedings of the Twenty-Fourth annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611973105.78"},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/102782.102783","article-title":"A random polynomial-time algorithm for approximating the volume of convex bodies","volume":"38","author":"Dyer","year":"1991","journal-title":"J. ACM"},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1006\/jcss.1999.1686","article-title":"On the limits of nonapproximability of lattice problems","volume":"60","author":"Goldreich","year":"2000","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_64","doi-asserted-by":"crossref","unstructured":"Bl\u00f6mer, J., and Naewe, S. (2007). Sampling methods for shortest vectors, closest vectors and successive minima. International Colloquium on Automata, Languages, and Programming, Springer.","DOI":"10.1007\/978-3-540-73420-8_8"},{"key":"ref_65","first-page":"3","article-title":"On bounds for packings on a sphere and in space","volume":"14","author":"Kabatiansky","year":"1978","journal-title":"Probl. Peredachi Informatsii"},{"key":"ref_66","unstructured":"Pisier, G. (1999). The Volume of Convex Bodies and Banach Space Geometry, Cambridge University Press."},{"key":"ref_67","unstructured":"Regev, O. (2009). Lecture Notes on Lattices in Computer Science, New York University."},{"key":"ref_68","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579403","article-title":"On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem","volume":"6","author":"Babai","year":"1986","journal-title":"Combinatorica"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/362\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:46:42Z","timestamp":1760168802000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/362"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,13]]},"references-count":68,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["a14120362"],"URL":"https:\/\/doi.org\/10.3390\/a14120362","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,12,13]]}}}