AF: Small: Computational and Geometric aspects of Lattices

AF：小：格子的计算和几何方面

• 批准号: 1814524
• 负责人: Oded Regev
• 金额: $ 50万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2021-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814524&HistoricalAwards=false
• 关键词: AF; Small; Computational; Geometric; aspects

This project focuses on lattice-based cryptography, an area born in the late 1990s, and that has since grown tremendously. Lattices are mathematical objects defined as the the set of all integer combinations of some n linearly independent vectors in n-dimensional Euclidean space. For instance, the set of all integer points in n-dimensional Euclidean space forms a lattice. For n=2, this is the set of all points in the familiar Cartesian plane with integer coordinates. Lattices have attracted the attention of mathematicians for over two centuries, and have an impressive number of applications in mathematics and computer science, from number theory and Diophantine approximation to complexity theory and cryptography. Lattice-based cryptography is unique in that it is believed to be secure against attacks using quantum computers, a feature not shared by any of the traditional cryptographic schemes such as RSA (named for its inventors' initials). Moreover, recent work has shown that lattice-based cryptography is practical, and that it is amazingly versatile, leading to a remarkable number of applications such as fully homomorphic encryption, which allows computation on encrypted data.The main goal of the project is establishing even stronger foundations for lattice-based cryptography by finding tighter hardness reductions and understanding the mysterious role quantum computing plays in it. The project also includes the development of new classical and quantum algorithms for lattice problems, as well as an investigation into some of the geometrical properties of 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.

该项目专注于基于格的密码学，这是一个诞生于20世纪90年代末的领域，此后发展迅速。格是数学对象，定义为n维欧氏空间中n个线性无关向量的所有整数组合的集合。例如，n维欧氏空间中所有整数点的集合形成一个格。对于n=2，这是在熟悉的笛卡尔平面上具有整数坐标的所有点的集合。格吸引了数学家的注意力超过两个世纪，并在数学和计算机科学中有令人印象深刻的应用，从数论和丢番图近似到复杂性理论和密码学。基于格的密码学是独特的，因为它被认为是安全的，可以抵御使用量子计算机的攻击，这是任何传统密码方案都不具备的特征，例如RSA（以其发明者的姓名首字母命名）。此外，最近的工作表明，基于格的密码学是实用的，而且它是惊人的通用，导致了显着数量的应用，如全同态加密，该项目的主要目标是为网格建立更坚实的基础，通过寻找更严格的硬度降低和理解量子计算在其中扮演的神秘角色，该项目还包括开发该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

New bounds on the density of lattice coverings

• DOI: 10.1090/jams/984
• 发表时间: 2020-05
• 期刊: ArXiv
• 作者: Or Ordentlich;O. Regev;B. Weiss

Concentration of Markov chains with bounded moments

具有有界矩的马尔可夫链的集中

• DOI: 10.1214/19-aihp1039
• 发表时间: 2020
• 期刊: Probabilités et Statistiques
• 作者: Naor, Assaf;Rao, Shravas;Regev, Oded
• 通讯作者: Regev, Oded

Continuous LWE

连续LWE

• DOI: 10.1145/3406325.3451000
• 发表时间: 2021
• 期刊: STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Bruna, Joan;Regev, Oded;Song, Min Jae;Tang, Yi
• 通讯作者: Tang, Yi

Nearly Optimal Embeddings of Flat Tori

平面 Tori 的近乎最佳嵌入

• 发表时间: 2020
• 期刊: APPROX 2020
• 作者: Agarwal, Ishan;Regev, Oded;Tang, Yi
• 通讯作者: Tang, Yi

The Minrank of Random Graphs

随机图的 Minrank

• DOI: 10.1109/tit.2018.2810384
• 发表时间: 2018
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Golovnev, Alexander;Regev, Oded;Weinstein, Omri
• 通讯作者: Weinstein, Omri