格点分布与格密码数学问题的求解算法研究

The computational hardness of cryptologic mathematical problems in lattices is the theoretical foundation of the security of lattice-based cryptosystems, and the research on algorithms for cryptologic mathematical problems in lattices is one of the core research fields in lattice-based cryptography, which is of great importance in both theory and application. On the one hand, algorithms for cryptologic mathematical problems in lattices can be directly converted into important tools for public-key cryptanalysis. On the other hand, algorithms for cryptologic mathematical problems in lattices are theoretical foundation for parameter setting in lattice-based cryptologic schemes. This project will study efficient algorithms for computational mathematical problems closely related to the security of cryptosystems in lattices. Concretely speaking, firstly，by utilizing the estimation on the numbers of lattice points in high-dimension geometrical bodies of different bounds, we study the efficiencies of enumeration in the corresponding bounds. Secondly, based on the properties of discrete ellipsoid distribution over lattices or other measures induced by associated convex bodies, we analyze and optimize the random algorithms. This project is a cross-theory fundamental research with promising applications. By combining the mathematical techniques with the thoughts in cryptographic theory, we try to improve and optimize the known algorithms both in theory and practice.

格密码数学问题的计算困难性是格密码体制安全性的理论基础，其求解算法的研究是基于格的密码学的核心研究领域，具有重要的理论意义与应用价值。一方面, 格密码数学问题的有效算法可以直接转化为公钥密码分析的重要工具。另一方面, 格密码数学问题的有效算法又可以为格密码体制设计中的参数选取提供理论依据。本课题将对与密码体制安全性密切相关的数学问题的求解算法展开研究。具体包含两个方面的研究内容：第一, 基于不同界下高维几何体内格点数目的估计，研究枚举算法在相应界下的效率。第二，基于格上离散椭球分布及其他凸体诱导下的格点位置分布敏感测度的研究，对格密码数学问题的随机算法进行分析和优化。本课题属于具有重要应用前景的基础交叉理论研究,尝试将数学技巧方法与密码理论中的思想方法相结合，从理论和实践上完善与优化现有的求解算法

格密码数学问题的困难性是基于格的密码体制安全性的理论基础，同时这些问题的求解算法在密码体制的安全性分析也具有重要作用。项目围绕格密码数学问题，取得了如下几个成果:(1)研究了无穷范数度量下二维格最短向量的快速求解算法。设计了基于Half-gcd的按分量约化的局部欧几里得算法,改进了经典的Lagrange 约化算法，使得求解该问题的时间复杂度由O(n^2)降为O(nlog^2n loglogn)。并将新算法用于序列的最短有理分数表示问题，实验效果表明，新算法比目前已有的最快算法效率提高了至少 90%。(2) 计算格基的Hermite正规型在格密码体制的设计中具有重要应用，但由于需要处理计算过程中系数膨胀问题，对大规模格基矩阵的求解计算量很大。项目研究并设计了云辅助的Hermite正规型快速求解算法，大大降低了本地端计算开销，同时该算法不仅可以保护本地端输入格基矩阵，而且可以验证云返回结果的正确性。(3) 大规模模线形方程组Ax=bmodq的求解是基于SIS与LWE问题的格密码体制的基本运算，基于格基矩阵的幺模矩阵变换技术与置换技术，我们设计了云辅助的外包求解算法，实现在保护输入矩阵与输出向量隐私前提下的高效算法，将本地端求解的复杂度由O(n^3)降为O(n^2)。 (4) 研究了云计算模式下的大整数模逆及大规模有限域模逆运算加速算法。给出了大整数以及有限域模逆运算安全外包加速算法。该算法通过把模逆问题转化为二维格格向量求解问题，利用二维格格基在幺模矩阵变换下的等价性，设计了一个安全高效的模逆运算外包算法，降低了本地端计算负担。