## 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**

**Lecture notes**

** 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.