随着量子算法和量子计算技术的进步，许多传统问题的困难性在量子计算的模型下受到了挑战，基于这类困难问题设计的密码体系的安全性也面临着量子计算技术的威胁，如： Shor 算法解决大整数分解问题、Grover 算法解决搜索问题等。为设计能够在后量子时代提供安全的密码体系，具有潜在抗量子攻击能力的困难问题受到了广泛关注，特别是基于格的困难问题。 格中最主要的两个困难问题分别是最短向量问题（SVP）和最近向量问题（CVP） 。对于格中的困难问题，当前主要的求解方法有：枚举算法、格基约化算法、采样算法、筛法等。 本文研究了与格困难问题相关的几类算法，包括：枚举算法、格基约化算法以及采样算法，并取得了三项主要的研究成果。其中，在枚举算法方面，本文提出了一种新型采样算法：正交枚举算法，该算法的关键技术是将向量的整数表示技术应用到枚举算法中，向量的整数表示技术能够体现最短向量的稀疏特征，基于该表示技术设计的枚举算法对比传统枚举算法可以大大减少枚举空间，在效率上达到指数级的提升，此外，正交枚举算法还具有参数选取更灵活、应用范围更广的特点；本文的第二个成果是提出了一种新的格基约化算法（MBKZ），其关键技术是交替使用了上述正交枚举算法与传统枚举算法作为格基约化算法的子模块， 由于两种枚举算法的枚举空间不同，能够有效地相互更新格基，从而避免了由随机化导致的计算冗余，提高了格基约化算法的效率；本文的第三个工作是对离散高斯采样算法的研究，可分为两个部分，第一部分提出了采样算法光滑参数的新的上界估计，光滑参数是衡量离散高斯分布与连续高斯分布差距的重要指标，关于光滑参数的估计直接关系到相关格密码体制设计中的参数选取； 第二部分则研究了离散高斯采样的卷积定理，在离散高斯采样算法中，卷积定理是一项重要的基本定理，它给出了多个有较小标准差的离散高斯采样的卷积与另一个有较大标准差的离散高斯采样分布接近的结论以及两者之间的误差。 本文研究了实际情况下离散高斯采样算法的卷积定理，在原有研究关注卷积误差的基础上引入了浮点数误差与截断误差，进而给出了更符合实践的误差估计，此外，本文首次提出不同的采样方法会导致不同的概率分布误差的结论，只有将具体采样方法和分析相结合才能得到与实验相符的误差估计，具有很大的现实意义。
With the fast development of quantum algorithms and quantum computing technologies, many hard problems can be much easier to be solved using a quantum computer in the future, which indicates that the cryptosystems based on these hard problems may become much weaker against quamtum attacks, i.e. Shor's algorithm for Large Integer Factoring Problem and Grover's algorithm for searching problem. In order to deal with this situation, many other hard problems which may resist quantum attacks have been widely studied, among which lattice based problems are the most popular ones. Shortest Vector Problem (SVP) and Closest Vector Problem (CVP) are the two most famous lattice problems which can transfer into each other under certain conditions. Many algorithms have been proposed to solve these problems including enumeration, lattice reduction, sampling algorithm and sieve algorithm. We study enumeration, lattice reduction and sampling algorithm of lattice problems in this paper. More specifically, we propose a new enumeration algorithm called orthognalized enumeration algorithm by utilizing orthogonalized integer representations technique, the new enumeration algorithm can achieve exponential speedups both in theory and in practice compared with former results. Besides, we use the orthognalized enumeration to form a new lattice reduction algorithm named MBKZ. In the former lattice reduction algorithms, i.e. BKZ and BKZ 2.0, the randomizing process which introduces extra overhead is necessary to avoid falling into a local optimal solution. However, the design of MBKZ solves this problem and also provides a much better efficiency. In addition, we propose two new bounds for smoothing parameter of discrete Gaussian sampling and a novel improved practical error estimation of convolution theorem of discrete Gaussian sampling. Smoothing parameter is an improtant tool to measure the difference between discrete Gaussian distribution and successive Gaussian distribution, and is widely used in designing lattice based systems. Moreover, the new proposed error estimation can be tightly matched by experiments because our analysis firstly takes truncation error as well as sampling method into consideration which are usually ignored in the former theoretical results.
