AF: Small: Computational and Geometric aspects of Lattices

New York University, New York NY

Investigators

Abstract

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.