Geometric objects called lattices have had countless essential applications in mathematics and the sciences. Recently, they have emerged as a new and very appealing foundation for cryptography, offering asymptotic efficiency, worst-case hardness guarantees, and apparent resistance to quantum computers.
This project is dedicated to a broad study of lattices in cryptography and related areas. Specifically, it addresses three main directions: (i) a foundational investigation into the worst-case and average-case complexity of lattice problems, and connections with number-theoretic problems such as factoring; (ii) constructions of essential cryptographic notions such as proof systems and pseudorandom objects; (iii) the design of efficient, practical algorithms supporting fast implementations of lattice-based schemes. Results from this project may one day lead to wide adoption of faster and more secure cryptography in a wide variety of computing and networking applications.
At the heart of any cryptographic protocol are assumptions about the scheme's operating environment and the attacker's interactions with it --- but more fundamentally, about the amount of computing resources required to break it. The past few decades have seen tremendous success in using an area of mathematics called "number theory" to build cryptography that provides rich functionality while withstanding very strong attempts at breaking the schemes. For instance, today's widely used cryptosystems are believed to be secure for hundreds of years, even when attacked by the most powerful computers ever designed. However, this security comes at a price: the systems are not especially efficient on today's (or tomorrow's) computing platforms. A further worry is that "quantum computers" can, in principle, completely break many of today's most widely used cryptosystems. While quantum computers have so far only been demonstrated at very small scales, their long-term possibility necessitates new approaches in cryptography.
Geometric objects called "lattices" have recently emerged as an entirely different, and very attractive, mathematical foundation for cryptography. Lattice-based schemes offer significant utility and efficiency, especially on highly parallel machines, and appear to be secure even in the face of quantum attacks. Due to their novelty, however, many basic questions are unanswered or entirely unexplored. This project conducts a broad study of lattices in cryptography, ranging from a foundational investigation of their hard problems and connections to other number-theoretic problems, to new designs of essential cryptographic objects and studies of their concrete efficiency and security.
