标题： 基于格的密码学背后的某些数学问题 显示英文标题

标题： Some Mathematical Problems Behind Lattice-Based Cryptography

摘要： 1994年，P. Shor发现了可以破解RSA密码系统和ElGamal密码系统的量子算法。 2007年，D-Wave展示了第一台量子计算机。 这些事件及进一步的发展给秘密通信带来了危机。 2016年，美国国家标准与技术研究院（NIST）启动了一个全球项目，征集并选择少数几种能够抵御量子计算机攻击的加密算法。 2022年，它宣布了四个候选算法，即CRYSTALS-Kyber、CRYSTALS-Dilithium、 Falcon和Sphincs$+$，用于后量子密码标准。 前三个基于格理论，最后一个基于哈希函数。 众所周知，基于格的密码系统的安全性依赖于最短向量问题（SVP）、最近向量问题（CVP）及其推广的计算复杂性。 事实上，SVP是一个球体包装问题，而CVP是一个球体覆盖问题。 此外，SVP和CVP都等价于正定二次型的算术问题。 因此，后量子密码学为数学家在现代技术中做出贡献提供了前所未有的机会。 本文将简要回顾基于格的密码学所建立的数学问题，以便数学家们能看到他们确实参与其中。 显示英文摘要

摘要： In 1994, P. Shor discovered quantum algorithms which 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 the Hash function. It is well known that the security of the lattice-based cryptosystems relies on the computational complexity of the shortest vector problem (SVP), the closest vector problem (CVP) and their generalizations. In fact, the SVP is a ball packing problem and the CVP is a ball covering problem. Furthermore, both SVP and CVP are equivalent to arithmetic problems for positive definite quadratic forms. Therefore, post-quantum cryptography provides unprecedented opportunities for mathematicians to make contributions in modern technology. This paper will briefly review the mathematical problems on which the lattice-based cryptography is built up, so that mathematicians can see that they are indeed in the game.