CSC2414 (Fall 2011)
Topics in Applied Discrete Mathematics: Lattices in Computer Science



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: 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

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): For the latter half of the course (Cryptography): The following is a good reference to learn about Lattices in computational Number Theory: