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.