COS 533 (Fall 2023)
Advanced Cryptography
Welcome! This is the course homepage for the Fall 2023 iteration of COS 533.
Course Title: Advanced Cryptography
Location and Time: Tuesdays and Thursdays 1:30-2:50pm, Green Hall 0-S-9
Instructor: Alex Lombardi (contact), Office Hours: Tuesdays 4pm, Computer Science 312
TA: Qianfan Zhang, Office Hours: Thursdays 3pm, Computer Science 233
Course Description: This course covers a selection of topics in cryptography, including some or all of the following: one-way functions, mathematical foundations of group-based and lattice-based cryptography, proof systems, multi-party computation, fully homomorphic encryption, obfuscation, and (post-)quantum cryptography. This course is intended to serve as an introduction to cryptography from the foundations up to present-day research.
Prerequisites: COS 240 or equivalent mathematical maturity. Cryptography at the level of COS 433 would be helpful but is not required. Undergraduates (in addition to graduate students) are welcome to take the course.
Course Requirements
Scribe Notes: Each student should write up scribe notes (in LaTeX) for one lecture. These notes may be posted on the course website. Sign up for scribing here.
Problem Sets: Due roughly once every two weeks.
Problem Set 1 (Due Thursday, 9/21 at 11:59pm)
Problem Set 2 (Due Thursday, 10/5 at 11:59pm)
Problem Set 3 (Due Thursday, 11/2 at 11:59pm)
Problem Set 4 (Due Thursday, 11/16 at 11:59pm)
Problem Set 5 (Due Thursday, 12/7 at 11:59pm)
Schedule
9/5: Introduction, Encryption. Scribe notes
9/7: PRGs, One-Way Functions. Scribe notes
9/12: Weak One-Way Functions. Goldreich-Levin Theorem (Part I)
9/14: Goldreich-Levin Theorem (Part II). PRGs from One-Way Functions
9/19: PRFs, Secret-key Encryption.
9/21: Factoring, discrete logarithms. Scribe notes
9/26: Public-Key Encryption. Algorithms for discrete log/factoring (Part I). Scribe notes. Reference: random factored integers
9/28: Algorithms for discrete log/factoring (Part II). Identification Schemes.
10/3: Zero-knowledge proofs (Part I)
10/5: Zero-knowledge proofs (Part II). Scribe notes
10/10: Digital Signatures and the Fiat-Shamir Heuristic (Part I)
10/12: Digital Signatures and the Fiat-Shamir Heuristic (Part II). Interactive proofs beyond NP.
10/17: No Class (Fall Recess)
10/19: No Class: (Fall Recess)
10/24: Succinct interactive proof systems. GKR.
10/26: GKR Continued. Succinct arguments for NP. Reference: GKR details
10/31: Oblivious transfer, secure two-party computation. Scribe notes
11/2: Secure multi-party computation (Part I)
11/7: Secure multi-party computation (Part II). Program Obfuscation
11/9: Program Obfuscation (Part II). Scribe notes
11/14: Lattice-based cryptography (Part I): SIS. Reference: Chapter 3 of Vaikuntanathan's course notes
11/16: Lattice-based cryptography (Part II): LWE.
11/21: No Class (Friday Schedule)
11/23: No Class (Thanksgiving)
11/28: Introduction to quantum computation. Reference: Aaronson's course, Chapters 16, 17, and 18.
11/30: Quantum Fourier Transform. Shor's algorithm (Part I)
12/5: Shor's algorithm (Part II). Regev's reduction (hardness of LWE). Scribe Notes
12/7: Overview of Quantum Cryptography