SaTC: CORE: Small: Modular, Efficient, Homomorphic Cryptography

现代计算机应用程序不仅需要使用加密来保护数据，而且还需要对加密形式的数据执行计算，例如在云计算环境中，其中私有数据被存储和处理在远程、不可信的服务器上。格密码学是数学密码学中一个快速发展的领域，它有可能为许多复杂的安全问题提供新的更好的解决方案，也是目前唯一已知的允许构造完全同态加密方案的技术：允许对加密数据执行任意计算的加密机制。格子密码学还提供了后量子安全，即它被认为可以抵抗量子计算机发展带来的未来威胁。该项目的创新之处在于引入了一个用于设计和分析同态加密函数的新框架，并使用它来提高对这一重要密码原语的理解，以及提高其效率。该项目的影响是使更好的方法能够安全地共享和使用数据(以加密形式)，并为正在进行的标准化后量子密码学和同态加密的努力提供信息。本项目研究基于格的复杂密码原语的模块化设计的一般框架，包括完全同态加密(FHE)。从满足某些弱线性同态性质的基本(私钥)加密方案出发，对各种已知的同态加密方案以及一些新的同态加密方案进行了统一、模块化的描述、比较、分析和组合。在这个框架内，研究了几个重要的问题。这个项目考虑的具体问题是：圆形安全FHE方案的设计，利用分期自举技术构建更有效的FHE方案，使用混合解决方案将不同的FHE方案结合在一起，以及基于秘密共享的安全多方计算形式，以及基于网格的多用途通用可合成不经意传输的构建。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Modern computer applications require not only to protect data using encryption, but also to perform computations on data in encrypted form, e.g., in a cloud computing setting where private data is stored and processed on a remote, untrusted server. Lattice cryptography is a fast-developing area of mathematical cryptography which has the potential to deliver new and better solutions to many complex security problems, and currently the only known technique allowing the construction of fully homomorphic encryption schemes: encryption mechanisms that allow to perform arbitrary computations on encrypted data. Lattice cryptography also offers post-quantum security, i.e., it is believed to resist the future threat posed by the development of quantum computers. The project's novelties are the introduction of a new framework for the design and analysis of homomorphic encryption functions, and its use to improve the understanding of this important cryptographic primitive, as well as to improve its efficiency. The project impacts are enabling better methods to securely share and use data (in encrypted form), and inform ongoing efforts to standardize post-quantum cryptography and homomorphic encryption.This project investigates a general framework for the modular design of complex cryptographic primitives based on lattices, including fully homomorphic encryption (FHE). Starting from a basic (private key) encryption scheme satisfying certain weak linear homomorphic properties, a variety of known homomorphic encryption schemes, as well as some new ones, are described in a unified, modular way, compared, analyzed and combined. Within this framework, several important problems are investigated. Specific questions considered in this project are: the design of circular secure FHE schemes, the construction of more efficient FHE schemes making use of amortized bootstrapping techniques, the use of hybrid solutions combining together different FHE schemes as well as forms of secure multiparty computation based on secret sharing, and the construction of multi-use universally composable oblivious transfer based on lattices.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.