AF: Small: Computational Foundations of Lattices

点击翻译按钮获取中文摘要

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.