# CO 789: Lattice-Based Cryptography (Fall 2015)

Instructor: David Jao. Office hours: MWF 2:30pm-3:20pm.

### Course materials

- Course outline (
*https:../../wiki/images/0/08/CO789-2015-outline.pdf*)

### External resources

- Chris Peikert's
*Lattices in Cryptography*course: Fall 2015 (*https://web.eecs.umich.edu/~cpeikert/lic15/*), Fall 2013 (*https://web.eecs.umich.edu/~cpeikert/lic13/*) - Oded Regev's
*Lattices in Computer Science*course: Fall 2009 (*http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2009/*), Fall 2004 (*http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/*) - Daniele Micciancio's
*Lattices Algorithms and Applications*course: Spring 2014 (*http://cseweb.ucsd.edu/classes/sp14/cse206A-a/*), Winter 2010 (*http://www-cse.ucsd.edu/classes/wi10/cse206a*), Spring 2007 (*http://www-cse.ucsd.edu/classes/sp07/cse206a*) - Vinod Vaikuntanathan's
*Advanced Topics in Cryptography: Lattices*course: Fall 2015 (*https://people.csail.mit.edu/vinodv/6876-Fall2015/*), Fall 2011 (*https://people.csail.mit.edu/vinodv/COURSES/CSC2414-F11/*) - Shai Halevi's
*Homomorphic Encryption and Lattices*course: Spring 2013 (*https://people.csail.mit.edu/shaih/columbia6261/*), Spring 2011 (*https://people.csail.mit.edu/shaih/lattices-and-HE-class/*)

### Lectures

- September 14: Lattices -- Definitions, examples, basis, fundamental region
- September 16: Existence of bases, Hermite normal form
- September 18: Gram-Schmidt orthogonalization, lower bounds for λ
_{1} - Sepetmber 21: Minkowski's theorem, upper bounds for λ
_{1} - September 23: LLL -- definition and algorithm
- September 25: LLL -- proof and applications
- September 28: SVP to CVP reduction, NP-hardness of CVP
- September 30: Search/decisional CVP equivalence, Babai's nearest plane algorithm
- October 2: Ajtai's OWF and CRHF, reduction to SIS
- October 5: Discrete Gaussian sampling, SIS to SIVP reduction
- October 7: Cyclic lattices and ideals
- October 9: SIS to SIVP reduction for cyclic lattices
- October 14: LWE and applications
- October 16: LWE reductions: Decision to search; self-reducibility
- October 19: LWE to BDD reductions
- October 21: Quantum LWE to SIVP reduction
- October 23: Ring-LWE: definition and applications
- October 26: Number fields, algebraic numbers, and the canonical embedding
- October 28: Algebraic integers and construction of integral bases
- October 30: RLWE cryptosystems; security proofs
- November 2: NTRU
- November 4: Lattice trapdoors
- November 6: IBE and HIBE
- November 9: Fully homomorphic encryption
- November 11: Attribute-based encryption
- November 13: Security proofs for ABE
- November 16: Software obfuscation
- November 18: Multilinear maps

### Schedule of course projects

- November 20: LWE cryptanalysis (Luis Ruiz-Lopez)
- November 23: BKZ lattice reduction (Sharat Ibrahimpur)
- November 25: Quantum cryptanalysis of Ajtai-Dwork (Jason LeGrow)
- November 27: GGH cryptosystem (Christopher Leonardi)
- November 30: Circuit squashing (Youngho Yoo)
- December 2: Fully homomorphic encryption (Emily Neufeld)
- December 4: Trapdoor signature schemes (Edward Eaton)