格密码学研究

Survey of Lattice-based Cryptography

格密码是一类备受关注的抗量子计算攻击的公钥密码体制.格密码理论的研究涉及的密码数学问题很多,学科交叉特色明显,研究方法趋于多元化.格密码的发展大体分为两条主线:一是从具有悠久历史的格经典数学问题的研究发展到近30多年来高维格困难问题的求解算法及其计算复杂性理论研究;二是从使用格困难问题的求解算法分析非格公钥密码体制的安全性发展到基于格困难问题的密码体制的设计.本文从格困难问题的计算复杂性研究、格困难问题的求解算法、格密码体制的设计以及格密码分析四个方面较为全面地回顾了格密码领域30多年来的主要研究成果,并试图体现四个研究领域方法的渗透与融合.此外,对与格密码理论研究有重要影响的一些格数学问题的经典研究方法与成果本文也进行了简单的描述.

Lattice-based cryptography is widely believed to resist quantum computer attacks, which involves many cryptographic mathematical problems and belongs to interdisciplinary study. The development of lattice-based cryptography follows two main lines: One is to study the computational complexity and searching algorithms for solving hard problems in high dimensional lattices based on the research of classical lattice problems. The other is to analyze the security of non-lattice-based public-key cryptosystems using the algorithms solving hard lattice problems, and further to design the lattice-based cryptosystems. This paper gives a survey of the main progress on lattice-based cryptography in recent 30 years, which covers the following concerns: computational complexity and searching algorithms relating to hard lattice problems, design and cryptanalysis of lattice-based cryptosystems. The paper tries to reflect the relationship of these four areas. In addition, some classical lattice problems and relative important results are described.