## EECS 598: Lattices in Cryptography (2015)

**Meeting:** Mondays and Wednesdays, 10:30a-12p, G. G. Brown Lab 1363

**First meeting:** Wednesday, Sep 9

**Instructor:** Chris
Peikert (`cpeikert ATHERE umich DOTHERE edu`)

**Office Hours:** Beyster 3601, by appointment

**Resources**

**Homeworks**

- Homework 1, due Wed 23 Sep. [PDF, LaTeX template, macros]
- Homework 2, due Wed 7 Oct. [PDF, LaTeX template, macros]
- Homework 3, due Web 4 Nov. [PDF, LaTeX template, macros]
- Homework 4, due Web 23 Nov. [PDF, LaTeX template, macros]

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

** 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, depending on
time and level of interest, 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, and the SIS/LWE problems
- Basic cryptographic constructions: one-way functions, encryption
schemes, digital signatures
- ``Exotic'' cryptographic constructions: identity-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*. Students should be
comfortable with devising and writing correct and clear formal proofs (and
finding the flaws in incorrect ones!), devising and analyzing
algorithms, and working with probability.
A previous course in cryptography (e.g., Applied/Theoretical
Cryptography) is helpful but is not required. No previous familiarity
with lattices will be assumed. *Highly recommended* courses (the
more the better) include: EECS 477 or 586 (Algorithms), EECS 574
(Computational Complexity Theory), EECS 575 (Advanced Cryptography).
The instructor reserves the right to limit enrollment to students who
have the necessary background.