Announcements

• Per Austrin will give the lecture on December 6 Tuesday. This will be the last day of the course. Happy Holidays!
• Problem Set 3 is online. Due December 22.
• Problem Set 2 is online. Due October 31 (deadline extended to November 4, Friday).
• The class has been moved to University College Room 87 (basement) for the remainder of the term. Click here for a map. Once you get in through the main entrance, you need to take the flight of stairs to your right down to the basement.
  
  
• Previous Announcements

Course Information

INSTRUCTOR	Vinod Vaikuntanathan Office: Sandford Fleming 2301B E-mail: vinodv@cs
LOCATION	Note, New Location for the rest of the term: University College UC 87. [ map ]
TIME	Tuesday 3 - 5pm, Office Hours Tuesday 5:10-6:10pm in SF2301B, or by appointment
TEXTBOOK	There are no required textbooks. Instead, we will use material from the references below. In addition, for the first few lectures, we may refer to the book Complexity of Lattice Problems: A Cryptographic Perspective Daniele Micciancio and Shafi Goldwasser. [ Link to the Amazon.ca page ]
GRADING	Based on four Problem Sets, Scribing 1-2 Lectures and Class Participation

All this information (and more) can be found in the course information sheet.

Course Description

Integer lattices are powerful mathematical objects that have found applications in many diverse facets of computer science, most notably in the areas of cryptography and combinatorial optimization. This course gives an introduction to the theory of integer lattices -- their algorithms and applications to combinatorial optimization, their recent use in cryptography culminating in the first construction of a fully homomorphic encryption scheme, and the fascinating complexity landscape associated with lattice problems. This course will touch several related areas and applications:

• Algorithms and Combinatorial Optimization: The asymptotically fastest Integer Programming algorithm known to date is based on lattices. We will study lattice algorithms and their applications to combinatorial optimization.
• Cryptography: Lattices have proven themselves to be a double-edged sword in cryptography. While they were first used to break cryptosystems, they have more recently been instrumental in designing a wide range of secure cryptographic primitives, including public key encryption, digital signatures, encryption resistant to key leakage attacks, identity based encryption, and most notably, the first fully homomorphic encryption scheme.

Prerequisites: We will assume knowledge of basic math (linear algebra and probability) and introductory level algorithms (analysis of algorithms, polynomial time and NP-hardness). We will NOT assume any prior knowledge of cryptography or advanced complexity theory.

Problem Sets

• Problem Set 1 posted, due Oct 3 at 11:59pm [pdf | tex]. Use the style file here to compile the tex.
• Problem Set 2 posted, due Oct 31 at 11:59pm [pdf | tex]. No style files needed to compile.
• Problem Set 3 posted, due Dec 22 at 11:59pm [pdf | tex]. No style files needed to compile.

Schedule (subject to change)

Lecture	Topic	Announcements	Scribe Notes
Lecture 1 (Sep 13)	Overview of the Course, Definitions of Lattices, Gram-Schmidt Orthogonalization, Successive Minima.	Problem Set 1 posted Sep 12, due Oct 3	Vinod Vaikuntanathan pdf, latex source and style file.
Lecture 2 (Sep 20)	Minkowski's Theorem and Applications in Number Theory		Serge Gorbunov Lightly edited notes pdf.
Lecture 3 (Sep 27)	Computational Problems on Lattices -- the Shortest Vector Problem and friends, the LLL algorithm		Devin Jeanpierre
Lecture 4 (Oct 4)	Applications -- Small Solutions to polynomial equations, Breaking various special cases of the RSA encryption, Integer Programming.		Wesley George Lightly edited notes pdf.
Lecture 5 (Oct 11)	Complexity of Lattice Problems, NP-hardness.		Joel Oren Lightly edited notes pdf.
Lecture 6 (Oct 18)	Dual Lattices and the Smoothing Parameter.	Problem Set 2 posted Oct 18, due Oct 31	Jan Gorzny
Lecture 7 (Oct 25)	Average-case Hardness of Lattice Problems, Ajtai's Worst-case to Average-case Reduction, Introduction to Lattice-based Cryptography.		Michael Tao
Lecture 8 (Nov 1)	Lattice-based Cryptography (contd.), One-way Functions, Collision-Resistant Hash Functions.		Yu Wu
Lecture 9 (Nov 15)	Learning with Errors (LWE), Search and Decisional versions of LWE and a Reduction, Lattice-based Secret- and Public-key Cryptography		Venkatesh Medabalimi
Lecture 10 (Nov 22)	Worst-case to Average-case Reduction for LWE.		David Kordalewski
Lecture 11 (Nov 29)	Fully homomorphic encryption and Applications, An LWE-based Fully Homomorphic Encryption System.	Problem Set 3 posted Dec 5, due Dec 22	Kirill Ignatiev
Lecture 12 (Dec 6)	LWE-based Fully Homomorphic Encryption System (contd.).

References

For the first half of the course (Foundations, Algorithms and Complexity of Lattice Problems):

• Oded Regev's course at Tel-Aviv University. The material in this course will be our primary reference.
• Daniele Micciancio's course at UCSD.

For the latter half of the course (Cryptography):

• Boaz Barak's courses at Princeton (Lectures 11-12), Princeton again (Lecture 19-22) and MIT (Lectures 2-3) for lattice-based cryptography and homomorphic encryption.
• Shai Halevi's course at Tel-Aviv University on homomorphic encryption.

The following is a good reference to learn about Lattices in computational Number Theory:

• Rings and Integer Lattices in Computer Science, lectures notes from the Bellairs-McGill workshop on Computational Complexity in 2007.

---