Historical Papers Seminar Series

Lattice Cryptography - From Complexity Theory to Fully Homomorphic Encryption

In 1996, Ajtai proved a remarkable connection between the average-case and worst-case complexity of lattice problems, which opened the door to the use of lattices in the design of secure cryptographic functions. That's also the year I started learning about cryptography, and made lattice cryptography my main research focus for the following 20 years. Today lattice cryptography is a thriving research area, providing one of the most attractive "post-quantum" alternatives to mainstream number theoretic cryptography, and offering powerful tools to attack the most challenging cryptographic problems like fully homomorphic encryption and program obfuscation. In this talk, I will go over the evolution of lattice cryptography, from an area of theoretical cryptography at the intersection with computational complexity, to the mature research area it is today.