NSFSaTC-BSF: CORE: Small: Foundations of Lattice-based Cryptography

在过去的二十年里，格已经成为密码学的强大数学基础。首先，基于格的密码学抵抗了量子攻击，而传统的密码系统在90年代中期屈服于它。其次，基于格的密码学在实现传统密码学无法实现的新的和令人兴奋的功能方面发挥了重要作用。最值得注意的例子可能是全同态加密（FHE）和一般的基于属性的加密（ABE），它们分别允许我们计算和实现加密数据的表达性访问控制。最后，它也表明，基本的基于格的结构，如数字签名，伪随机函数和密钥交换可以非常有效，以至于我们现在越来越有兴趣从政府（NSA和NIST）和行业（谷歌）部署基于格的加密解决方案。我们奋进的成功将产生超越密码学的影响：在数据和计算越来越多地外包的世界中为隐私问题提供新的解决方案，并在后量子时代提供安全性。该项目的目标有三个方面：（a）基于格的新密码构造：尽管我们在构造诸如全同态的高级密码原语方面已经取得了很大的进步，基于属性的加密和基于函数的加密在标准格问题上，例如带错误学习问题，还有很多工作要做。也许最突出的目标是提出一个程序混淆的结构（因此，几乎所有的密码学）基于标准格问题的难度;（B）有效的基于格的密码学：我们的目标是提高现有密码构造的效率，从伪随机函数一直到同态和基于属性的加密，一个奋进，这是在翻译理论的进步转化为实际有用的对象具有巨大的重要性;和（三）基础的硬度格问题：我们的目标是推进和深化我们的理解的硬度密码相关的格问题。该项目涉及一个重要的教育组成部分，包括设计密码学新课程，公开提供讲义，进行临时讲座，编写面向广大受众的调查文章和专著，组织一系列研讨会和一个关于格的讲习班，并为研究生和本科生提供咨询。

Over the last two decades, lattices have emerged as a powerful mathematical basis for cryptography. For one, Lattice-based Cryptography has resisted quantum attacks while conventional crypto systems succumbed to it in the mid-90s. Secondly, Lattice-based Cryptography has been instrumental in realizing new and exciting functionality which is beyond the reach of conventional cryptography. The most notable examples, perhaps, are Fully Homomorphic Encryption (FHE) and general Attribute Based Encryption (ABE) which, respectively, allow us to compute on and achieve expressive access control of encrypted data. Finally, it has also been shown that basic lattice-based constructions such as digital signatures, pseudorandom functions and key exchange can be made very efficient, to the point that we now have growing interest from the government (NSA and NIST) and the industry (Google) in deploying lattice-based cryptographic solutions. Success in our endeavor will have implications beyond the cryptography: enabling new solutions for privacy concerns in a world where data and computations are increasingly being outsourced, as well as providing security in a post-quantum era.The goal of this project is three-fold: (a) New Cryptographic Constructions from Lattices: although we have made great strides in constructing advanced cryptographic primitives such as fully homomorphic, attribute based and functional encryption on standard lattice problems such as the learning with errors problem, much is left to be done. Perhaps the most prominent goal is to come up with a construction of program obfuscation (and thus, nearly all of cryptography) based on the hardness of standard lattice problems; (b) Efficient Lattice-based Cryptography: we aim to improve the efficiency of existing cryptographic constructions, starting from pseudorandom functions all the way to homomorphic and attribute-based encryption, an endeavor that is of tremendous importance in translating theoretical advances into practically useful objects; and (c) Foundations of Hardness of Lattice Problems: we aim to advance and deepen our understanding of the hardness of cryptographically relevant lattice problems. The project involves a significant educational component that consists of designing new courses in cryptography, making the lecture notes publicly available, giving expository lectures, writing survey articles and monographs intended for a broad audience, organizing a seminar series and a workshop on lattices, and advising graduate and undergraduate students.