格上困难问题最坏情况到平均情况的紧归约

There exists a big gap between the reduction factor from worst-case to average-case on lattice problems and the approximate factor within which certain lattice problems can be proved to be NP-hard. This project focuses mainly on the reduction from the worst-case GapSIVP_γ/GapSVP_γ/GapCRP_γ to the average-case SIS problem, including the following key steps. 1. Establish the connection between the smoothing parameter and other lattice parameters, and determine the lower bound on the smoothing parameter. 2. Generalize the analytical method from the spherical case to the non-spherical one, and propose new methods for sampling random lattices points and for generating random SIS instances. 3. Determine the Euclid norm of the lattice points that obey the non-spherical Gaussian distribution, establish the connection between the solution of the SIS problem and the parameters of the IncIDV_(γ,g)^φ, and accomplish the reduction from the worst-case GapSIVP_γ/GapSVP_γ to the average-case SIS problem. 4. Establish the connection between the solution of the SIS problem and the parameters of the SDP_γ, and accomplish the reduction from the worst-case GapCRP_γ to the average-case SIS problem. This project lays emphasis on the basic research of lattice cryptography. We hope that the project can help us to make a breakthrough on the reduction from the worst-case to the average-case, thus providing stronger security guarantee for the lattice schemes based on the SIS problem.

格上困难问题由最坏情况到平均情况的归约因子和特定问题可证NP困难的近似因子之间存在较大的间隙（间隙越小密码方案越安全）。本项目旨在研究格上最坏情况GapSIVP_γ/GapSVP_γ/GapCRP_γ到平均情况SIS问题的紧归约，包括如下关键步骤：建立格上光滑参数和其他参量之间的关联，明确光滑参数的下确界；将格上离散高斯分析方法推广至非球面情况，提出新型随机格点采样技术及随机SIS实例的生成方法；界定服从非球面离散高斯分布格点的欧式范数，建立SIS实例的解和IncIDV_(γ,g)^φ参数之间的关联，完成GapSIVP_γ/GapSVP_γ到SIS问题的紧归约；建立SIS实例的解和SDP_γ参数之间的关联，完成GapCRP_γ到SIS问题的紧归约。本项目注重格公钥密码底层理论的研究，希望在最坏情况到平均情况的格归约理论方面有一定的突破，为基于SIS问题的格密码方案提供更强的安全保障。

SIS问题是奠定格公钥密码安全基础的两大困难问题之一。本项目主要研究平均情况下SIS问题与最坏情况下GapSVP/GapSIVP/GapCRP之间的归约关系。研究方法上的主要创新是提出了格上非球面高斯分析方法，突破了原有格上球面高斯原像采样算法中高斯参数的最优值，提升了基于原像采样算法的密码方案的安全性和效率，研究成果主要贡献是：（1）提出一种适用于任意模数的G-lattice上的非球面离散高斯采样算法，渐近效率达到最优，并且运行过程中只需少量的存储空间和浮点数运算；（2）提出一种改进的非球面离散高斯搅扰向量采样算法，可以同时提高原像采样算法的安全性并降低参数尺寸。.本项目研究的基于非球面高斯的原像采样算法有很强的使用价值，研究方法也有独特之处，可用于格上数字签名的实例化，并推动格上高级密码方案的实用化。