Key Information
Overview
The modern computing environment is very different than it used to be. Sensitive information that once existed only on local trusted machines—medical records, personal preferences, and our finances—is now stored and processed by various entities on the web, who we often do not trust. To maintain privacy and integrity in this reality, a new array of cryptographic tools has been developed over the past decade and a half allowing different forms of encrypted computation. This includes: advanced multi-party computation protocols, fully-homomorphic encryption, attribute-based encryption, functional encryption, and program obfuscation. The course will cover some of these advances.
Tentative list of topics
- Secure Multiparty Computation: Information theoretic and computational, Garbled Circuits and Randomized Encodings
- Lattice Crypto Basics: SIS, LWE, Trapdoors
- Fully-Homomorphic Encryption: GSW, Bootstrapping
- Attribute-based and Functional Encryption
- Laconic Function Evaluation
- Program Obfuscation: Definitions, Barriers, Applications, Constructions
The topic list is tentative. The selection and depth of coverage may vary.
Grading
| Component | Weight |
|---|---|
| Participation | 5% |
| Homework | 45% |
| Final Exam | 50% |
Participation includes both participation in class and on the course forum.
The final exam will mostly include variants of HW questions. If you solved those yourselves, you would have a significant advantage.
Prerequisites
An intro-level course in cryptography, basic probability theory, basic algorithms or complexity (basic familiarity with P, NP). Perhaps the most important prerequisite is mathematical maturity: the ability to read, understand, and write mathematical proofs.
Schedule
The schedule will be updated throughout the semester.
| Date | Topic | HW | Due | Extra Reading |
|---|---|---|---|---|
| Jan 20 | ||||
| Jan 27 | ||||
| Feb 3 | ||||
| Feb 10 | ||||
| Feb 17 | ||||
| Feb 24 | ||||
| Mar 3 | ||||
| Mar 10 | ||||
| Mar 17 | No class — Spring Break | |||
| Mar 24 | ||||
| Mar 31 | ||||
| Apr 7 | ||||
| Apr 14 | ||||
| Apr 21 | ||||
| Apr 28 | Final Exam |
Resources
Related courses and background references. Course-specific readings will be added to the schedule.
- From Lattices to Program Obfuscation, Vinod Vaikuntanathan (MIT, Fall 2024)
- Computing on Encrypted Data, Daniel Wichs (Northeastern, Spring 2024)
- Topics in Cryptography, David Wu (UT Austin, Spring 2024)
- An Intensive Introduction to Cryptography, Boaz Barak
- Foundations of Cryptography, Oded Goldreich
Course Policies
Homework
There will be about 5 homework assignments during the semester. Homework should be submitted in PDF form in Gradescope. Submissions should be typeset in LaTeX. These days, you don't need to know LaTeX; you can use AI tools.
You will be graded not only for correctness, but also clarity. If you do not understand how to solve a question, you may write “I don't know how to do this,” and you will receive 15% credit for that question.
Collaboration
We strongly encourage you to discuss assignments with your peers, but you must (a) list the names of your discussion partners on your submission, and (b) write up your solution on your own.
Academic Integrity
Your work should be your own. Students should be aware of the CS Department's Policy on Academic Integrity. Violations of academic integrity will not be tolerated.
AI
AI is likely to be able to solve all of your homework. We will not prevent you from using AI to solve your homework. However, if you do use AI, please list the exact model as a collaborator, and add as an appendix your prompts. We strongly suggest that you do your best to solve the questions yourselves. The final exam will mostly include variants of HW questions. If you solved those yourselves, you would have a significant advantage.
Religious Observance
As a nonsectarian, inclusive institution, NYU policy permits members of any religious group to absent themselves from classes without penalty when required for compliance with their religious obligations. The policy and principles to be followed by students and faculty may be found in the University Calendar Policy on Religious Holidays.
Disability Disclosure
Academic accommodations are available to any student with a chronic, psychological, visual, mobility, learning disability, or who is deaf or hard of hearing. Students should please register with the Moses Center for Students with Disabilities.