格上计算问题的算法与复杂性研究

Lattice-based cryptosystems are the most important public-key cryptosystems in post quantum age and they also have various applications in cloud computing age nowadays. Nevertheless, the research on their security is not sufficient. To have a better assessment on the theoretical security of lattice-based cryptosystems, this project focuses on the algorithms and complexity of computational problems in lattice. In the aspect of algorithms, we study how to define, describe and generate “random full-rank integer lattice” more reasonably to evaluate and predict the output qualities of general lattice algorithms like LLL. These results can be used to choose parameters of lattice-based cryptosystems for reference; we also study how to design specific SVP/CVP algorithms in ideal lattice according to its special structure for the analysis of cryptosystems based on ideal lattice problems. In the aspect of complexity, we study how to improve the randomized reduction proving SVP is NP-hard given by Micciancio to evaluate the security of lattice-based cryptosytems more efficiently. Thus, this project is of great scientific and application value.

基于格的公钥密码体制是后量子时代最重要的公钥密码体制，也在如今的云计算时代下有广泛的应用，可是对其安全性的研究还不充分。为了更好地评估基于格的公钥密码体制的理论安全性，本项目拟研究格上计算问题的算法与复杂性。在算法方面，我们拟研究如何更合理地定义、刻画及生成随机满秩整格，用于评测及预测LLL等一般格算法的实际输出质量，为基于格的公钥密码体制的参数选取提供参考；我们还研究如何利用理想格的特殊结构设计其上SVP/CVP的特定求解算法，用于分析基于理想格上格问题的公钥密码体制；而在复杂性方面，我们拟研究如何改进Micciancio给出的证明SVP是NP难问题的随机归约，用于更有效地评估基于格的公钥密码体制的安全性。因此，本项目具有重要的科学意义和应用价值。

本项目主要研究了格上计算问题SVP, CVP的算法与复杂性。通过反向采样，提出了一种更为高效的随机整格生成算法，用作格算法的输入，可用于测评格算法的平均输出质量；对于低维数的主理想格，证明其SVP解的格基表示系数范围较小，其SVP解可直接给出，对于CVP也有类似结果；合作提出一种基于格问题的支持k-bit算术操作的全同态加密体制，随着k的增加，其对称加密与公钥加密的密文扩张分别会趋近于1和2。