CSC2414 (Fall 2011)
Topics in Applied Discrete Mathematics: Lattices in Computer Science
Topics in Applied Discrete Mathematics: Lattices in Computer Science
INSTRUCTOR  Vinod Vaikuntanathan
Office: Sandford Fleming 2301B Email: 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:106: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 12 Lectures and Class Participation 
Lecture  Topic  Announcements  Scribe Notes 
Lecture 1 (Sep 13)  Overview of the Course, Definitions of Lattices, GramSchmidt 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, NPhardness. 
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)  Averagecase Hardness of Lattice Problems, Ajtai's Worstcase to Averagecase Reduction, Introduction to Latticebased Cryptography.  Michael Tao  
Lecture 8 (Nov 1)  Latticebased Cryptography (contd.), Oneway Functions, CollisionResistant Hash Functions.  Yu Wu  
Lecture 9 (Nov 15)  Learning with Errors (LWE), Search and Decisional versions of LWE and a Reduction, Latticebased Secret and Publickey Cryptography  Venkatesh Medabalimi  
Lecture 10 (Nov 22)  Worstcase to Averagecase Reduction for LWE.  David Kordalewski  
Lecture 11 (Nov 29)  Fully homomorphic encryption and Applications, An LWEbased Fully Homomorphic Encryption System. 
Problem Set 3 posted Dec 5, due Dec 22 
Kirill Ignatiev 
Lecture 12 (Dec 6)  LWEbased Fully Homomorphic Encryption System (contd.). 