Lattices in Theoretical Computer Science and Cryptography - Some Snippets from a >40-Year History

Abstract:

We will try to tell some of the story of lattices in theoretical computer science and cryptography.

We start with (1) the celebrated LLL algorithm from 1982—an incredibly useful algorithm that solves a seemingly not-so-useful problem—and the central role that lattices played in breaking many early cryptographic schemes.

We will then move to (2) Ajtai’s amazing worst-case to average-case reduction from 1996, showing how to build secure secret-key cryptography under the assumption that a certain *worst-case* *approximate* lattice problem is hard. We will then see how around the same time, (3) Ajtai proved that the exact version of this problem was NP-hard (resolving a decades-old open question), which was followed by a series of NP-hardness of approximation results with progressively larger approximation factors. Together, these results led to speculation and hope that lattice techniques might lead us to one of the holy grails of cryptography: proof that cryptography exists under the minimal assumption that BPP =/= NP---all one had to do was show NP-hardness for an approximation factor large enough to be compatible with Ajtai's worst-case to average-case reduction!

This hope was basically quashed by (4) Goldreich and Goldwasser's simple and elegant 1998 proof system for approximate lattice problems, suggesting that NP-hardness was unlikely.  Though this result largely ruled out a very exciting line of research, it also introduced powerful and beautiful tools that have found innumerable applications in lattice cryptography and beyond.

Finally, we will discuss (5) Regev's worst-case to average-case reduction from 2005, showing how to build secure *public-key* cryptography, again under the assumption that a certain worst-case approximate lattice problem is hard. This result led to a revolution in cryptography, with applications ranging from fully homomorphic encryption to the post-quantum cryptographic schemes that will be running the internet shortly.

And, time permitting, I’ll say a bit about my own work in this field.

Bio:

Noah is an assistant professor in Cornell's computer science department. His research to date has focused primarily on the study of lattices. He is also interested more broadly in theoretical computer science, cryptography, and geometry. He received his PhD from NYU, advised by Professors Oded Regev and Yevgeniy Dodis. Before coming to Cornell, he was a fellow at the Simons Institute in Berkeley, a postdoctoral researcher at MIT's computer science department, and a postdoc at Princeton’s computer science department.