Beyond the Bootcamp:
CS 294-168 Lattices, Learning with Errors and Post-Quantum Cryptography



Course Description

The study of integer lattices, discrete additive subgroups of Rn, serves as a bridge between number theory and geometry and has for centuries received the attention of illustrious mathematicians including Lagrange, Gauss, Dirichlet, Hermite and Minkowski.

The role of lattices in cryptography has been revolutionary and dramatic. In the 80s and the early 90s, lattices served as a destructive force, giving the cryptanalysts some of their most potent attack tools.

In the last two decades, the Learning with Errors (LWE) Problem, whose hardness is closely related to lattice problems, has revolutionized modern cryptography by giving us (a) a basis for "post-quantum" cryptography, (b) a dizzying variety of cryptographic primitives such as fully homomorphic encryption and signatures, attribute-based and functional encryption, a rich set of pseudorandom functions, various types of program obfuscation and much more; and finally, (c) a unique source of computational hardness with worst-case to average-case connections. This course explores the various facets of lattices, the LWE problem and their applications in cryptography.

The course is intended to complement the Spring'20 Simons Institute program on Lattices. In particular, to get more out of the course, the students are encouraged to attend the bootcamp and the workshops of the program.

Prerequisites: This is an advanced course, intended for beginning graduate students and upper level undergraduates in CS and Math. Mathematical maturity and comfort with linear algebraic notions is the most important pre-requisite, followed by courses in the theory of computation (CS 172 or equivalent) and cryptography (CS 171 or CS 276).

Course Information

INSTRUCTOR Vinod Vaikuntanathan
E-mail: vinodv at berkeley dot edu
LOCATION Soda 320
TIME M 5pm - 7:30pm (with a break in between),
Office Hours by appointment
TEXTBOOK There are no required textbooks. Instead, we will use lecture notes and papers from the references listed below, as well as instructor's notes.
GRADING Based on (a) class participation (come to class; attend a talk of your choice in each of the three workshops, and write a short email to the instructor with a review of the talk, including a summary, what you liked/disliked and any ideas you got from watching it) and (b) a final project (either come up with a new result -- talk to the instructor for project ideas -- or write a short survey on a topic that will be useful to future researchers).

Announcements


Schedule (tentative and subject to change)

Lecture Topic References
Lecture 1 (Jan 27) Introduction to SIS and LWE. Basic properties and cryptographic applications: public and private-key encryption and collision-resistant hashing. Instructor notes
Lecture 2 (Feb 3) Algorithms for LWE. Introduction to Lattices. Instructor notes
References
Lecture 3 (Feb 10) Smoothing Parameter and Worst-case to Average-case Reduction for SIS. Instructor notes
References
Feb 17 President's Day (No Class)
Lecture 4 (Feb 24) Reductions for LWE (Worst-to-average case, Search-to-decision) Instructor notes (updated 3/2)
References
Lecture 5 (Mar 2) Pseudorandom Functions and Learning with Rounding. Instructor notes
References
Lecture 6 (Mar 9) Lattice Trapdoors and Discrete Gaussian Sampling.
Digital Signatures.
Instructor notes
References
Mar 16 Class canceled
Mar 23 Spring Break (No Class)
Lecture 7 (Mar 30) Identity-based Encryption and Hierarchical IBE. Instructor notes
References
Lecture 8 (Apr 6) Fully Homomorphic Encryption. The key equation and applications to attribute-based encryption, fully homomorphic signatures and constrained pseudorandom functions. Instructor notes
References
Lecture 9 (Apr 13) The GGH15 Multilinear Map and Applications. Instructor notes
References
Lecture 10 (Apr 20) Ideal Lattices and Ring Learning with Errors. Instructor notes
References
Lecture 11 (Apr 27) AMA on lattices with Vinod.
Lecture 12 (May 4) Lattices and Quantum Computing. Instructor notes
References


References

Courses Elsewhere:

Lecture 2

Lecture 3

Lecture 4

Lecture 5

Lecture 6

Lecture 7

Lecture 8

Lecture 9

Lecture 10

Lecture 12