The 25th McGill Invitational Workshop on Computational Complexity will be held at Bellairs Research Institute of McGill University, Holetown, St. James, Barbados, West Indies from February 22nd to March 1st, 2013. Participants are expected to arrive on Friday afternoon, February 22nd. The subject of this year's workshop will be Lattices and Lattice-Based Cryptography.

Speaker:

Oded Regev

New York University

Lattices and Lattice-Based Cryptography

Over the last three decades, the computational study of lattices has witnessed several remarkable discoveries. Most notable are the development of the LLL algorithm by Lenstra, Lenstra and Lovasz and Ajtai's discovery of lattice-based cryptographic constructions. In this workshop we will explore these and other more recent developments in the area.

After an introduction to the area, including a description of the LLL algorithm, we will describe some recent progress on the computational complexity of lattice problems, such as NP-hardness results, containment in coNP, and the connection to quantum computation. In the process, we will develop the mathematical techniques of Gaussian measures and Fourier analysis, and introduce the so-called smoothing parameter.

The rest of the workshop will be devoted to application in cryptography, especially through the short integer solution problem (SIS) and the learning with errors problem (LWE). We will prove that these problems are as hard as worst-case lattice problems, and then proceed to describe some of the remarkable variety of cryptographic constructions that can be based on them. Time permitting, we will also discuss some very recent developments, such as practical lattice-based cryptography based on ideal lattices, lattice-based fully homomorphic encryption, and classical hardness of the learning with errors problem.