AF: Small: Computational Foundations of Lattices

格是数学对象，定义为n维欧氏空间中一些n个线性无关向量的所有整数组合的集合。例如，n维欧氏空间中所有整数点的集合形成一个格。格吸引了伟大的数学家的注意超过两个世纪，并在数学和计算机科学中有令人印象深刻的应用，从数论和丢番图近似到复杂性理论和密码学。该奖项专注于基于网格的密码学，这是一个诞生于90年代末的领域，此后发展迅速。基于格的密码学提供了可能是传统数论密码学（如RSA）的唯一替代方案，并拥有强大的可证明安全性，针对量子计算机的安全性，实用和高度优化的实现，惊人的多功能性，导致大量的应用，该奖项的广泛目标是回答基于格的密码学领域中一些主要和最具挑战性的开放问题。这些问题包括：基于格的密码学是否可以证明上级传统密码学？我们能否为基于格的密码学获得更好的安全性证明，例如证明理想格的硬度陈述？利用数论的技术，这些问题的进展应该是可能的。该奖项还解决了有关晶格问题的计算复杂性的相关问题，例如所谓的最短向量问题的难度。最后，该奖项解决了一个基本的问题，在几何的格子，进展应该有应用程序的其余目标的奖项，以及数学和计算研究的格子一般。用于凸几何中密切相关问题的技术似乎特别有前途。总之，如果算法数论或量子计算机实现方面取得进展，基于格的密码学很可能是最好的（甚至可能是唯一的）手段，让人类重新使用现代密码学，因为它几乎用于我们生活的任何方面，包括信用卡，在线金融交易，安全的电话交谈，以及更多。该奖项将进一步加深我们对基于格的密码学的理解，并将致力于使其达到取代传统密码学的水平。

Lattices are mathematical objects defined as 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. Lattices have attracted the attention of great 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. The award focuses on lattice-based cryptography, an area born in the late 90s, and that has since grown tremendously. Lattice-based cryptography offers what is possibly the only alternative to traditional number-theoretic cryptography such as RSA, and boasts strong provable security, conjectured security against quantum computers, practical and highly optimized implementations, amazing versatility leading to a remarkable number of applications, and more.The broad goal of the award is to answer some of the main and most challenging open questions in the area of lattice-based cryptography. These include: Is lattice-based cryptography provably superior to traditional cryptography? Can we obtain better security proofs for lattice-based cryptography, such as proving hardness statements for ideal lattices? Progress on these questions should be possible using techniques from number theory. The award also addresses related questions regarding the computational complexity of lattice problems, such as the hardness of the so-called shortest vector problem. Finally, the award addresses a fundamental question in the geometry of lattices, progress on which should have applications to the rest of the goals of the award, as well as to the mathematical and computational study of lattices in general. Techniques used for closely related questions in convex geometry seem particularly promising.In summary, in the event of progress in algorithmic number theory or advances in the implementation of quantum computers, lattice-based cryptography is most likely the best (and possibly even only) means for humanity to reclaim modern cryptography as used in nearly any aspect of our lives, including credit cards, online financial transactions, secure phone conversations, and lots more. The award will further our understanding of lattice-based cryptography, and will aim to bring it to the point at which it is ready to replace traditional cryptography.