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

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

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.

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

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