Collaborative Research: AF: SaTC: Medium: Theoretical Foundations of Lattice-Based Cryptography

格是几何对象，在计算机科学，特别是安全密码学的设计中有着广泛的应用。这种基于格的密码术具有许多吸引人的特性，包括它即使在对抗配备了量子计算机的对手时也具有明显的安全性(被称为“后量子”)，以及它在构造高级原语方面的有用性，包括允许“对加密数据进行计算”的完全同态加密(FHE)。基于此，美国国家标准与技术研究所(NIST)最近选择了几个基于格的密码系统进行标准化，作为其长达数年的后量子密码学标准化进程的一部分。由于基于格的密码系统将在不久的将来得到广泛使用，了解其背后问题的复杂性(安全性)显得尤为迫切。首先，该项目试图更好地理解格问题的细粒度复杂性，即解决基于格的密码系统所需的计算问题所需的精确运行时间。理想情况下，这项工作将有助于更好地理解这些密码系统的实际安全性。其次，这个项目将研究格和纠错码之间的联系，它们与格有许多相似之处，本身就是重要的和深入研究的对象。第三，这个项目将研究代数结构格上问题的复杂性。基于这些格子的密码系统-包括大多数实用的密码系统，包括NIST最近选择进行标准化的那些-通常效率要高得多，但人们对它们背后问题的复杂性知之甚少。除了这些主要的研究目标外，研究人员还将编写一本关于计算机科学中的晶格的全面、免费的教科书。特别是，这本书将详细地涵盖晶格的算法、复杂性理论、密码学和几何方面。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Lattices are geometric objects that have many applications in computer science, and especially to the design of secure cryptography. Such lattice-based cryptography has many attractive properties including its apparent security even against adversaries equipped with quantum computers (being "post-quantum") and its usefulness in constructing advanced primitives, including Fully Homomorphic Encryption (FHE), which allows for "computing on encrypted data." Based on this, the National Institute of Standards and Technology (NIST) recently selected several lattice-based cryptosystems for standardization as part of their years-long post-quantum cryptography standardization process. As lattice-based cryptosystems will be in widespread use in the near future, it is especially urgent to understand the complexity (security) of the problems that underlie them.This project has three primary research goals. First, the project seeks to better understand the fine-grained complexity of lattice problems, i.e., the precise running time necessary to solve the computational problems underlying lattice-based cryptosystems. This work will ideally lead to a better understanding of the practical security of these cryptosystems. Second, this project will study connections between lattices and error-correcting codes, which have many similarities to lattices and are important and well-studied objects in their own right. Third, this project will study the complexity of problems on algebraically structured lattices. Cryptosystems based on these lattices---which include most practical cryptosystems, including those recently selected for standardization by NIST---are generally much more efficient, but much less is known about the complexity of the problems that underlie them. In addition to these main research goals, the investigators will write a comprehensive, freely available textbook about lattices in computer science. In particular, this book will cover algorithmic, complexity-theoretic, cryptographic, and geometric aspects of lattices in detail.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.