CS 8803 LIC: Lattices in Cryptography 2013

Meeting: Mondays and Wednesdays, 1-2:30pm, Cherry Emerson 204
First meeting: Monday, August 26
Instructor: Chris Peikert (cpeikert ATHERE cc.gatech.edu)
Office Hours: Klaus 3146, by appointment
Links:

Homeworks

Homework 1, due Wed 11 Sep. [PDF, LaTeX template, macros]
Homework 2, due Wed 25 Sep. [PDF, LaTeX template, macros]
Homework 3, due Wed 16 Oct. [PDF, LaTeX template, macros]

Lecture notes Updated/additional lecture notes are now kept here.

Lecture 1: Mathematical Background
Lecture 2: SVP, Gram-Schmidt, LLL
Lecture 3: LLL, Coppersmith
Lecture 4: Coppersmith, Cryptanalysis
Lecture 5: Cryptanalysis of Knapsack Cryptography
Lecture 6: Algorithms for SVP, CVP

Course description
Point lattices are remarkably useful in cryptography, both for cryptanalysis (breaking codes) and more recently for constructing cryptosystems with unique security and functionality properties. This seminar will cover classical results, exciting recent developments, and several important open problems. Specific topics will include:

Mathematical background and basic results
The LLL algorithm, Coppersmith's method, and applications to cryptanalysis
Complexity of lattice problems: NP-hardness, algorithms and other upper bounds
Gaussians, harmonic analysis, and the smoothing parameter
Worst-case/average-case reductions (SIS and LWE)
Basic cryptographic constructions: one-way functions, encryption schemes, digital signatures
``Exotic'' cryptographic constructions: ID-based encryption, fully homomorphic encryption and more
Ring-based cryptographic reductions and primitives

Prerequisites
There are no formal prerequisite classes. However, this course is mathematically rigorous, hence the main requirement is mathematical maturity. Specifically, students should be comfortable with devising and writing correct formal proofs (and finding the flaws in incorrect ones!), devising and analyzing algorithms and reductions between problems, and working with probability. A previous course in cryptography (e.g., Applied/Theoretical Cryptography) will be helpful but is not required. No previous familiarity with lattices will be assumed. Highly recommended courses include CS 6505 (Algorithms, Computability and Complexity), CS 6520 (Computational Complexity Theory), CS 6260 (Applied Cryptography), and/or CS 7560 (Theory of Cryptography). The instructor reserves the right to limit enrollment to students who have the necessary background.