{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T20:05:17Z","timestamp":1776197117833,"version":"3.50.1"},"reference-count":58,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T00:00:00Z","timestamp":1770854400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012166","name":"973 Program","doi-asserted-by":"crossref","award":["2013CB834201"],"award-info":[{"award-number":["2013CB834201"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["NSFC12226006"],"award-info":[{"award-number":["NSFC12226006"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["NSFC11921001"],"award-info":[{"award-number":["NSFC11921001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>In 1994, P. Shor discovered quantum algorithms that can break both the RSA cryptosystem and the ElGamal cryptosystem. In 2007, D-Wave demonstrated the first quantum computer. These events and further developments have brought a crisis to secret communication. In 2016, the National Institute of Standards and Technology (NIST) launched a global project to solicit and select a handful of encryption algorithms with the ability to resist quantum computer attacks. In 2022, it announced four candidates, CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, and Sphincs+, for post-quantum cryptography standards. The first three are based on lattice theory and the last on a hash function. The security of lattice-based cryptosystems relies on the computational complexity of the shortest vector problem (SVP), the closest vector problem (CVP), and their generalizations. As we will explain, the SVP is a ball-packing problem, and the CVP is a ball-covering problem. Furthermore, both the SVP and CVP are equivalent to arithmetic problems for positive definite quadratic forms. This paper will briefly describe the mathematical problems on which lattice-based cryptography is built so that cryptographers can extend their views and learn something useful.<\/jats:p>","DOI":"10.3390\/cryptography10010010","type":"journal-article","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T12:05:46Z","timestamp":1770897946000},"page":"10","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Some Mathematical Problems Behind Lattice-Based Cryptography"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1063-5918","authenticated-orcid":false,"given":"Chuanming","family":"Zong","sequence":"first","affiliation":[{"name":"Center for Applied Mathematics, Tianjin University, Tianjin 300072, China"}]}],"member":"1968","published-online":{"date-parts":[[2026,2,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New directions in cryptography","volume":"22","author":"Diffie","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A public key cryptosystem and a signature scheme based on discrete logarithms","volume":"31","author":"ElGamal","year":"1985","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","first-page":"417","article-title":"Use of elliptic curves in cryptography","volume":"Volume 218","author":"Miller","year":"1985","journal-title":"Conference on the Theory and Application of Cryptographic Techniques"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1090\/S0025-5718-1987-0866109-5","article-title":"Elliptic curve cryptosystems","volume":"48","author":"Koblitz","year":"1987","journal-title":"Math. Comput."},{"key":"ref_6","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, Santa Fe, NM, USA."},{"key":"ref_7","first-page":"317","article-title":"Shor\u2019s discrete logarithm quantum algorithm for elliptic curves","volume":"3","author":"Proos","year":"2003","journal-title":"Quantum Inf. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3708471","article-title":"An Efficient Quantum Factoring Algorithm","volume":"72","author":"Regev","year":"2025","journal-title":"J. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Ajtai, M., and Dwork, C. (1997, January 4\u20136). A public-key cryptosystem with worst-case\/average-case equivalence. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, TX, USA.","DOI":"10.1145\/258533.258604"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., and Halevi, S. (1997). Public-key cryptosystems from lattice reduction problems. Annual International Cryptology Conference, Springer.","DOI":"10.1007\/BFb0052231"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Hoffstein, J., Pipher, J., and Silverman, J.H. (1998). NTRU: A ring-based public key cryptosystem. International Algorithmic Number Theory Symposium, Springer.","DOI":"10.1007\/BFb0054868"},{"key":"ref_12","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 ACM Symposium on Theory of Computing, Baltimore, MD, USA.","DOI":"10.1145\/1060590.1060603"},{"key":"ref_13","unstructured":"Gentry, C. (June, January 31). Fully homomorphic encryption using ideal lattices. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Baaquie, B.E., and Kwek, L.-C. (2023). Quantum Computers, Theory and Algorithms, Springer.","DOI":"10.1007\/978-981-19-7517-2"},{"key":"ref_15","unstructured":"Alvarado, M., Gayler, L., Seals, A., Wang, T., and Hou, T. (2023). A survey on post-quantum cryptography: State-of-the-art and challenges. arXiv."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"767","DOI":"10.1134\/S1990478923040087","article-title":"Post-Quantum Cryptosystems: Open Problems and Solutions. Lattice-Based Cryptosystems","volume":"17","author":"Malygina","year":"2023","journal-title":"J. Appl. Ind. Math."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Hoffstein, J., Pipher, J., and Silverman, J.H. (2008). An Introduction to Mathematical Cryptography, Springer.","DOI":"10.1007\/978-0-387-77993-5_6"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Micciancio, D., and Goldwasser, S. (2002). Complexity of Lattice Problems: A Cryptographic Perspective, Kluwer Academic.","DOI":"10.1007\/978-1-4615-0897-7"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Micciancio, D., and Regev, O. (2009). Lattice-based cryptography. Post-Quantum Cryptography, Springer.","DOI":"10.1007\/978-3-540-88702-7_5"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"0801","DOI":"10.34133\/research.0801","article-title":"The mathematical foundation of post-quantum cryptography","volume":"8","author":"Zong","year":"2025","journal-title":"Research"},{"key":"ref_21","unstructured":"van Emde Boas, P. (1981). Another NP-Complete Problem and the Complexity of Computing Short Vectors in a Lattice, Department of Mathmatics, University of Amsterdam. Tecnical Report."},{"key":"ref_22","unstructured":"Ajtai, M. (1998, January 24\u201326). The shortest vector problem in L2 is NP-hard for randomized reductions. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, Dallas, TX, USA."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579403","article-title":"On Lova\u00b4sz\u2019 lattice reduction and the nearest lattice point problem","volume":"6","author":"Babai","year":"1986","journal-title":"Combinatorica"},{"key":"ref_24","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":"Inform. Process. Lett."},{"key":"ref_25","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_26","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_27","first-page":"1","article-title":"Generating hard instances of lattice problems","volume":"13","author":"Ajtai","year":"2004","journal-title":"Quad. Mat."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1561\/0400000074","article-title":"A Decade of Lattice Cryptography","volume":"10","author":"Peikert","year":"2014","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"ref_29","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. Ser. B"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Zhang, J., and Zhang, Z. (2020). Lattice-Based Cryptosystems: A Design Perspective, Springer.","DOI":"10.1007\/978-981-15-8427-5"},{"key":"ref_31","unstructured":"Goldwasser, S. (2002). Mathematical Foundations of Modern Cryptography: Computational Complexity Perspective, Higher Education Press."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1137\/22M1486959","article-title":"Improved classical and quantum algorithms for the shortest vector problem via bounded distance decoding","volume":"54","author":"Aggarwal","year":"2025","journal-title":"SIAM J. Comput."},{"key":"ref_33","first-page":"24","article-title":"Extrait d\u2019une lettre adresse\u00e9e \u00e0 M Hermite","volume":"17","author":"Minkowski","year":"1893","journal-title":"Bull. Sci. Math."},{"key":"ref_34","unstructured":"Rogers, C.A. (1964). Packing and Covering, Cambridge University Press."},{"key":"ref_35","unstructured":"Zong, C. (1999). Sphere Packings, Springer."},{"key":"ref_36","unstructured":"Klartag, B. (2025). Lattice packing of spheres in high dimensions using a stochastically evolving ellipsoid. arXiv."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.4007\/annals.2017.185.3.8","article-title":"The sphere packing problem in dimension 24","volume":"185","author":"Cohn","year":"2017","journal-title":"Ann. Math."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"991","DOI":"10.4007\/annals.2017.185.3.7","article-title":"The sphere packing problem in dimension 8","volume":"185","author":"Viazovska","year":"2017","journal-title":"Ann. Math."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"577","DOI":"10.2307\/1971436","article-title":"Covering minima and lattice-point-free convex bodies","volume":"128","author":"Kannan","year":"1988","journal-title":"Ann. Math."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1937","DOI":"10.1155\/IMRN.2005.1937","article-title":"Local covering optimality of lattices: Leech lattice versus root lattice E8","volume":"32","author":"Schurmann","year":"2005","journal-title":"Int. Math. Res. Not."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1112\/plms\/s3-25.4.721","article-title":"Simultaneous packing and covering in euclidean space","volume":"25","author":"Butler","year":"1972","journal-title":"Proc. Lond. Math. Soc."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1137\/S0097539703433511","article-title":"Almost perfect lattices, the covering radius problem, and applications to Ajtai\u2019s connection factor","volume":"34","author":"Micciancio","year":"2004","journal-title":"SIAM J. Comput."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1090\/S0273-0979-02-00950-3","article-title":"From deep holes to free planes","volume":"39","author":"Zong","year":"2002","journal-title":"Bull. Amer. Math. Soc."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Wang, X., and Sako, K. (2012). Some mathematical mysteries in lattices (Abstract of a plenary talk). Advances in Cryptology\u2014ASIACRYPT 2012, Springer.","DOI":"10.1007\/978-3-642-34961-4"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1107\/S2053273316011682","article-title":"The complete classification of five-dimensional Dirichlet-Voronoi polyhedra of translational lattices","volume":"72","author":"Garber","year":"2016","journal-title":"Acta Crystallogr. Sect. A"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1007\/s00222-025-01325-0","article-title":"Voronoi conjecture for five-dimensional parallelohedra","volume":"240","author":"Garber","year":"2025","journal-title":"Invent. Math."},{"key":"ref_47","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_48","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/s10473-025-0106-x","article-title":"On generalized kissing numbers of convex bodies","volume":"45","author":"Li","year":"2025","journal-title":"Acta Math. Sci."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Conway, J.H., and Sloane, N.J.A. (1999). Sphere Packings, Lattices and Groups, Springer.","DOI":"10.1007\/978-1-4757-6568-7"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1112\/jlms\/s1-28.3.309","article-title":"On positive definite quadratic forms","volume":"28","author":"Rankin","year":"1953","journal-title":"J. Lond. Math. Soc."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Martinet, J. (2003). Perfect Lattices in Euclidean Spaces, Springer.","DOI":"10.1007\/978-3-662-05167-2"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"209","DOI":"10.5802\/jtnb.712","article-title":"A note on the Hermite-Rankin constant","volume":"22","author":"Sawatani","year":"2010","journal-title":"J. Theor. Nombres Bordeaux"},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Gama, N., Howgrave-Graham, N., Koy, H., and Nguyen, P.Q. (2006). Rankin\u2019s constant and blockwise lattice reduction. Advances in Cryptology-CRYPTO, Springer.","DOI":"10.1007\/11818175_7"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1597036.1597050","article-title":"Low-dimensional lattice basis reduction revisited","volume":"5","author":"Nguyen","year":"2009","journal-title":"ACM Trans. Algorithms"},{"key":"ref_55","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_56","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_57","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1017\/S1446788700011484","article-title":"Minkowski\u2019s fundamental inequality for reduced positive quadratic forms","volume":"26","author":"Barnes","year":"1978","journal-title":"J. Austral. Math. Soc. Ser. A"},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF02392364","article-title":"Die Reduktionstheorie der positiven quadratischen Formen","volume":"96","year":"1956","journal-title":"Acta Math."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/10\/1\/10\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T05:23:00Z","timestamp":1771046580000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/10\/1\/10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,12]]},"references-count":58,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,2]]}},"alternative-id":["cryptography10010010"],"URL":"https:\/\/doi.org\/10.3390\/cryptography10010010","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,12]]}}}