Computer Science

0368.4282

Fall 2004 
Lectures 
Monday 12:0015:00 
Instructor 
Oded Regev  Schreiber 220  5379  Office hours: Monday 15:0016:00 or by appointment 
Textbooks 
Complexity of Lattice Problems, D. Micciancio and S. Goldwasser, An Algorithmic Theory of Numbers, Graphs, and Convexity, L. Lovasz 
Lecture Notes 
Lattices in Cryptography and Cryptanalysis,
a course given by Daniele Micciancio Lattices and Their Application to Cryptography, a course given by Cynthia Dwork Algebra and Computation, a course given by Madhu Sudan. 
Other Links 
Complexity of SVP  A reader's digest, by R. Kumar and D. Sivakumar, nicely explains some of the topics covered in this class CaLC 2001, a conference on lattices, some papers can be found online Finding Small Solutions to Small Degree Polynomials, a paper by Coppersmith Twenty years of attacks on the RSA cryptosystem, a survey by Dan Boneh Lattice Basis Reduction and Integer Programming, by Karen Aardal, nicely explains fixeddimension integer programming using LLL basis reduction 
Date 
Class Topic 
Oct 18  Cancelled 
Oct 25  Basic definitions, GramSchmidt orthogonalization, successive minima, lower bound on succ. minima, Minkowski's convex body theorem 
Nov 1  Minkowski's first and second theorem, basic computational problems 
Nov 8  LLL algorithm, Babai's nearest plane algorithm 
Nov 15  Small solutions to small degree polynomials 
Nov 17  Integer programming in constant dimension, basic reductions 
Nov 22  GoldreichGoldwasser proof of GapCVP in coAM 
Nov 29  AjtaiKumarSivakumar SVP algorithm 
Dec 6  Dual lattices 
Dec 13  Fourier analysis 
Dec 20  Cancelled 
Dec 27  Transference theorems 
Dec 31  Worstcase to averagecase reduction 
Jan 3  Worstcase to averagecase reduction 
Jan 10  CVP with preprocessing 
Jan 17  Cancelled 