CS 671: Topics in Lattice-Based Cryptography

Fall 2022

General Information

Instructor: Leo Fan.
Office hours: by appointment -- please email me at any time.
The course meets Tuesday from 12:10 - 3:10 at BRR-5085.

Announcements

Potential course projects.
Scribing schedule.
Course project proposal is due Oct. 21.
Homework 1 is posted. Due Oct. 28.
Course project report is due Dec. 18.

Course Overview

This class is a graduate-level introduction to lattie-based cryptography. The lattices have significantly empowered modern cryptography by giving us (a) a basis for cryptosystems which are secure against quantum computers, (b) multiple breakthroughs in cryptographic primitives such as fully homomorphic encryption and signatures, attribute-based encryption, which are widely used in privacy-preserving machine learning. This course explores the various aspects of the lattices and their applications in cryptography.

There is no required textbook for this class — lectures, notes, and research papers are the main source of content. The following lecture notes and monograph from similar courses are very helpful:

Lattices, Learning with Errors and Post-Quantum Cryptography, by Vinod Vaikuntanathan.
A decade of lattice cryptography, by Chris Peikert.
Lattices in Computer Science, taught by Oded Regev at NYU.

Prerequisites: There are no formal prerequisite classes. A previous course in cryptography is helpful but is not required. This course is mathematically rigorous, hence the mathematical maturity and comfort with linear algebraic notions are the most important pre-requisite, followed by courses in the theory of computation.

Course Requirements

It is expected that students taking this course are interested in potential research in this area and, as such, none of the requirements will present a problem for anyone taking the class. The requirements are:

Regular attendance and participation during lecture.
Reading assigned references, which will be listed in advance of lecture.
Finishing homework assignments (about 3), due approximately every three weeks. Collaboration and external sources are allowed and encouraged; see academic honesty policy for details. This will count for 40% of the grade.
Scribing lecture notes (in latex) in small groups. This will count for 20% of the grade. The number of lectures to be scribed by each student will depend on how many students take the class. When scribing notes, please use this preamble. This sample file illustrates how to use it.
Conducting Research-oriented project and presentation. The projects do not need to be purely theoretical. This will count for 40% of the grade.

Academic Honesty

You are free to discuss the problem sets with others. However, the actual writeup of your assignments must be done ONLY by yourself (and without copying from notes or other sources!). In addition, you must acknowledge your sources and the discussions in your submission. Please read the Academic Integrity Policy for full details. If you are having trouble with the course, come speak to me!for full details. If you are having trouble with the course, come speak to me!

Schedule (subject to change)

Lecture	Topic	References
Lecture 1 (09/06)	Brief introduction to cryptography and lattices.	On the Growth of Cryptogaphy, by Rivest. A Decade of Lattice Cryptography, Section 2.1, 2.2.
Lecture 2 (09/13)	LWE, PKE and SKE from LWE, discrete Gaussian.	A Decade of Lattice Cryptography, Section 2.3, 4.2, 5.2.
Lecture 3 (09/20)	CCA-secure PKE, homomorphic encryption.	Secure Integration of Asymmetric and Symmetric Encryption Schemes by Fujisaki and Okamoto. A Decade of Lattice Cryptography, Section 5.4.3, 6.1.
Lecture 4 (09/27)	Bootstrapping in FHE, key-exchange.	Homomorphic Encryption by Shai Halevi. LWE-based Key Exchange by Joppe Bos, et al.
Lecture 5 (10/04)	Dual Regev PKE, attribute-based encryption.	A Decade of Lattice Cryptography, Section 5.2.1 - 5.2.3, 6.2.2 Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE, and Compact Garbled Circuits by Boneh et al.
Lecture 6 (10/11)	Attribute-based encryption (cont'd).	Attribute-Based Encryption for Circuits by Gorbunov et al.
Lecture 7 (10/18)	Predicate encryption and functional encryption.	Predicate Encryption for Circuits from LWE by Gorbunov et al. Functional Encryption with Bounded Collusions via Multi-Party Computation by Gorbunov et al.
Lecture 8 (10/25)	Lattice trapdoors and digital signatures.	A Decade of Lattice Cryptography, Section 5.4, 5.5. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert.
Lecture 9 (11/01)	Lattice trapdoors and digital signatures.	A Decade of Lattice Cryptography, Section 5.4, 5.5. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert.
Lecture 10 (11/08)	Fiat-Shamir transformation, Sigma protocol.	A Decade of Lattice Cryptography, Section 5.6. On Sigma-protocols by Damgard.
Lecture 11 (11/15)	Sigma protocol, Multi-key FHE.	Two Round Multiparty Computation via Multi-Key FHEby Mukherjee and Wichs
No Lecture (11/22)	Thanksgiving recess.
Lecture 12 (11/29)	Homomorphic commitment, DV-NIZK	A Decade of Lattice Cryptography, Section 6.1. Construction of a Non-Malleable Encryption Scheme from Any Semantically Secure One by Pass, shelat and Vaijuntanathan.
Lecture 13 (12/06)	DV-NIZK	A Decade of Lattice Cryptography, Section 6.1. Construction of a Non-Malleable Encryption Scheme from Any Semantically Secure One by Pass, shelat and Vaijuntanathan.
Lecture 14 (12/13)	Correlation-intractable hash functions and projects presentation.	Fiat-Shamir From Simpler Assumptions by Canetti et. al. Fiat-Shamir: From Practice to Theory, Part II NIZK and Correlation Intractability from Circular-Secure FHE by Canetti et. al.