Course Title: Cryptography
Location and Time: Tuesdays and Thursdays 11am-12:20pm, CS 104
Instructor: Alex Lombardi, Office Hours: Thursdays 12:30pm-1:30pm, CS 312
TAs:
Shreyas Gandlur, Office Hours: Tuesdays 5pm-6pm, Friend Center 010B
Yaxin Tu, Office Hours: Mondays 2pm-3pm, CS 401
Yuanhao Wang, Office Hours: Wednesdays 3pm-4pm, Friend Center 010A
Staff (Prof & TA) Email Address: cos433staff@princeton.edu
Course Description: An introduction to the theory of modern cryptography. Topics covered include private key and public key encryption schemes, digital signatures, pseudorandom generators and functions, zero-knowledge proofs, and some advanced topics.
Prerequisites: COS 240 or equivalent mathematical maturity.
Problem Sets
Problem sets will be assigned roughly once per week, with 8 in total. Problem sets will typically be released on Fridays at 11:59pm Eastern Time and due exactly one week later. UPDATE: problem sets will be due on Wednesdays starting from problem set 3, due October 2nd (see below).
Every problem set will have a "COS 433" section and a "COS 533" section; students enrolled in COS 433/533 should turn in solutions for the appropriate section. COS 433 students may submit solutions to COS 533 problems for (minor) extra credit, but are encouraged to prioritize the COS 433 problems and only attempt the advanced problems if they are looking for a challenge.
Enrolled students should submit solutions to the problem sets on Gradescope. Solutions must be typed; we strongly encourage typesetting solutions in LaTeX.
All problem sets will be posted below over the course of the semester.
Problem Set 1. Release Date: 9/6/24. Due Date: 9/13/24
Problem Set 2. Release Date: 9/13/24. Due Date: 9/20/24
Problem Set 3. Release Date: 9/20/24. Due Date: 10/2/24 (updated)
Problem Set 4. Release Date: 10/1/24. Due Date: 10/9/24
Problem Set 5. Release Date: 10/23/24. Due Date: 10/30/24
Problem Set 6. Release Date: 10/30/24. Due Date: 11/13/24
Problem Set 7. Release Date: 11/13/24. Due Date: 11/20/24
Problem Set 8. Release Date: 11/20/24. Due Date: 12/4/24
Collaboration Policy
You are free (and strongly encouraged!) to collaborate with each other on problem sets. Please adhere to the following policies regarding collaboration and attribution.
Individually write up problem set solutions in your own words. You may not share write-ups with your collaborators.
List all student collaborators and consulted outside sources (e.g. textbooks) in your problem set solutions.
You may not consult large language models or AI assistants such as (Chat)GPT.
Late Submission and Homework Grading Policy
You may take up to two late days for any problem set. These extensions are granted automatically (no need to ask permission!). We cannot accept any submissions that are more than two days late. If you have an extenuating circumstance such as a medical emergency, please reach out to the course staff.
To encourage timely submission, two bonus points (out of 100) will be granted to submissions that are on time.
We will automatically drop your lowest problem set grade, so no single week will negatively impact your grade.
Take home final exam (COS 433 only)
COS 433 students will have a take-home final exam in December (during Finals Period). Students may not collaborate with each other or consult external sources while taking the Final Exam. However, you may use the textbooks and slides linked to directly on this website.
Time Period: Monday, 12/16 7am - Wednesday, 12/18 7am.
The exam will be available on gradescope.
Final Project (COS 533 only)
COS 533 students will do a final project that is either an original exposition of a topic not covered in this class, or (if you are interested in doing cryptography research) original research in cryptography. A suggested list of exposition topics will be provided.
Scribe Notes (COS 533 only)
Each student enrolled in COS 533 is required to write up scribe notes (in LaTeX) for one lecture. These notes may be posted on the course website. Sign up to scribe here.
Your Course Grade
In COS 433, your grade will be based on Problem Sets (70%) and the Take-Home Final Exam (30%)
In COS 533, your grade will be based on Problem Sets (60%), Scribing (10%), and the Final Project (30%)
9/3: Introduction, Secret-Key Encryption. Lecture slides. KL Chapter 1
9/5: Perfect Secrecy. Lecture slides. KL Chapter 2
9/10: Computational Security. Lecture slides. KL Chapter 3, Sections 3.1-3.2
9/12: Pseudorandom Generators. Lecture slides. KL Chapter 3, Sections 3.3-3.4.1
9/17: CPA-secure Encryption. Lecture Slides. KL Sections 3.4.2-3.5,
9/19: Pseudorandom Functions. Lecture Slides. KL Sections 3.5, 8.5 (3rd Ed) ////// 3.6.1-3.6.2, 6.5 (1st Ed)
9/24: PRFs continued. Pseudorandom Permutations (Block Ciphers). Lecture Slides. KL Sections 3.5, 8.6 (3rd Ed) ////// 3.6.3-3.6.4, 5.2, 6.6 (1st Ed)
9/26: PRPs continued, Authentication. Lecture Slides. KL Sections 4.1-4.3 (3rd Ed) ////// 4.1-4.4, (1st Ed)
10/1: Authentication, CCA-secure Encryption. Lecture Slides. KL Chapter 5 (3rd Ed) ////// 3.7, 4.8 (1st Ed)
10/3: One-Way Functions, Hard-Core Predicates. Lecture Slides. KL Section 8.1 (3rd Ed) ////// 6.1 (1st Ed)
10/8: Goldreich-Levin Theorem. Lecture Slides. KL Section 8.3 (3rd Ed) ////// 6.3 (1st Ed). See also Sections 2.0, 2.2, and 3 of these notes (warning: the notes are somewhat dense).
10/10: Cryptography from Number Theory (Part I). Lecture Slides. KL Chapter 9, Section 10.2 (3rd Ed) ////// Chapter 7, Section 8.2 (1st Ed). Notes on Computational Number Theory.
10/15: No Class (Fall Recess)
10/17: No Class: (Fall Recess)
10/22: Cryptography from Number Theory (Part II), Public-Key Encryption. Lecture Slides. KL Chapter 9, Section 10.2 (3rd Ed) ////// Chapter 7, Section 8.2 (1st Ed).
10/24: Cryptography from Number Theory, Public-Key Encryption (Part III). Lecture Slides. KL Chapter 9, Section 10.2 (3rd Ed) ////// Chapter 7, Section 8.2 (1st Ed).
10/29: Discrete Logarithms (PKE Part IV). Lecture Slides.
10/31: Digital Signatures (Part I). Lecture Slides. KL Sections 13.1, 13.2, 13.4.1 (3rd Ed)
11/5: Class Cancelled
11/7: Digital Signatures (Part II). Hash functions and Random Oracles. Bellare-Rogaway Paper. KL Chapter 6 (3rd Ed). Boneh-Shoup Chapter 13.
11/12: Digital Signatures (Part III): RSA and DSA. Lecture Slides. Boneh-Shoup Chapter 13
11/14: Zero-Knowledge Proofs (Part I). Lecture Slides. Goldreich Chapter 4
11/19: Zero-Knowledge Proofs (Part II). Lecture Slides. Goldreich Chapter 4
11/21: Zero-Knowledge Proofs (Part III). Homomorphic Encryption (Part I). Peikert Sections 4.2, 5.2. Vaikuntanathan's Lecture Notes.
11/26: No Class (Friday Schedule)
11/28: No Class (Thanksgiving)
12/3: Learning with Errors, Homomorphic Encryption (Part II): Fully Homomorphic Encryption. Peikert Section 6.1. Vaikuntanathan's Lecture Notes.
12/5: Homomorphic Encryption (Part III). Delegation of Computation.
Textbooks
There is no official textbook for this course. The textbook most relevant to COS 433 is Katz and Lindell.
Boneh-Shoup and Goldreich are somewhat more advanced textbooks.
These lecture notes by Angluin are a useful reference on computational number theory.
Course Websites
The courses most closely related to this one are CS 127 at Harvard, 6.875 at MIT, and prior iterations of COS 433 at Princeton. However, none of these courses map exactly onto this one; in particular, we will depart fairly significantly from previous versions of COS 433.
Advanced Readings:
Notes on One-Way Functions and Pseudorandom Generators
Tutorials on the foundations of cryptography (ed. Yehuda Lindell)