COS 433 - Cryptography (Spring 2017)
Course Information
| Instructor: | Mark Zhandry ( ) |
| Office Hours: Mondays 3-4pm (COS 314) | |
| TA: | Fermi Ma ( ) |
| Office Hours: Fridays 2-3pm (Theory lounge, COS 3rd floor) | |
| Lecture: | MW 1:30am - 2:50pm, Room TBA |
| Grading: | 50% for roughly weekly homeworks, 20% take-home midterm, 30% take-home final |
| Piazza: | https://piazza.com/princeton/spring2017/cos433mat473_s2017 |
| Textbook: | There is no official text for this course, however Introduction to Modern Cryptography by Katz and Lindell (KL) is a good resource. Each lecture will have pointers to the appropriate sections of KL for those following along with the book. |
Course Description
Cryptography is an ancient practice dating back almost 4000 years. However, cryptography practiced today is very different than the cryptography used as recently as a few decades ago. For one, traditional cryptography was mostly synonymous with encryption: translating data into secret codes. Today, however, cryptography extends far beyond basic codes to encompass concepts such as authentication and integrity, and can be used to solve seemingly impossible tasks such as public key encryption (exchanging secret messages without ever having met in person to share a secret key) and zero knowledge proofs (proving theorems without revealing the proof).Another new feature in modern cryptography is its foundations. Until recently, cryptography was largely an art form based on intuition and ad hoc tweaks to block vulnerabilities. Modern crytpography is instead more of a science, characterized by rigorous mathematical definitions and theorems that guide the design of new systems.
This course is an introduction to modern cryptography, focusing on the theoretical foundations, with some attention to practical considerations. We will cover a variety of topics, including secret key and public key encryption, authentication, commitments, pseudorandom generators, and zero knowledge proofs.
Prerequisites: Basic probability theory. Basic complexity theory (as in COS340) recommended. No programming knowledge is required, though there may be an occasional extra credit exercise that will involve minimal programming (in a language of your choice).
Tentative Schedule (subject to change)
| Lecture | Topic | KL Section | Notes |
| 1 - M, 2/6 | Course introduction, A Brief History of Cryptography | 1.3 | [1] |
| 2 - W, 2/8 | Definitions in Cryptography, the One-time Pad | 1.4-2.2 | [2] |
| 3 - M, 2/13 | Multiple Message Security, Issues, Randomized Encryption | [3] | |
| 4 - W, 2/15 | Limitations of Information-Theoretic Security, Stream Ciphers, PRGs, and Computational Assumptions | 2.3-3.3 | [4] |
| 5 - M, 2/20 | Constructing PRGs | 6.1 | [5] |
| 6 - W, 2/22 | CPA security and PRFs | 3.4-3.5 | [6] |
| 7 - M, 2/27 | PRPs, Block Ciphers, Modes of Operation | 3.6, 6.2 | [7] |
| 8 - W, 3/1 | Constructing Block Ciphers | 6.2 | [8] |
| 9 - M, 3/6 | Attacks on Block Ciphers | 6.2 | [9] |
| 10 - W, 3/8 | Message Integrity, MACs | 4.1-4.4, 4.6 | [10] |
| 11 - M, 3/13 | Authenticated Encryption, CCA Security | 4.5 | [11] |
| 12 - W, 3/15 | Collision Resistant Hashing, Random Oracle Model | 5.1-5.4, 6.3 | [12] |
| M, 3/20 | No Class - Spring Break | ||
| W, 3/22 | |||
| 13 - M, 3/27 | Commitment Schemes | [13] | |
| 14 - W, 3/29 | Number-theoretic constructions of symmetric primitives | 8.3-8.4 | [14] |
| 15 - M, 4/3 | One-way permutations, hardcore predicates | 7.1 | [15] |
| 16 - W, 4/5 | Relationships between Symmetric Primitives | 7.2 | [16] |
| 17 - M, 4/10 | Diffie Hellman Key Exchange | 10.3 | [17] |
| 18 - W, 4/12 | Public Key Encryption | 11.1-11.4 | [18] |
| 19 - M, 4/17 | RSA, Trapdoor Permutations | 11.5, 13.1 | [19] |
| 20 - W, 4/19 | Digital Signatures | 12.1-12.4 | [20] |
| 21 - M, 4/24 | Digital Signatures from One-way Functions | 12.6 | [21] |
| 22 - W, 4/26 | Identification Protocols | 12.5 | [22] |
| 23 - M, 5/1 | Zero Knowledge | [23] | |
| 24 - W, 5/1 | CCA-secure Public Key Encryption without Random Oracles | [24] | |
Handouts
Basic Number TheoryHomework Assignments
Homework 1 (Due Feb 14)Homework 2 (Due Feb 21)
Homework 3 (Due Feb 28)
Homework 4 (Due Mar 7)
Homework 5 (Due April 4)
Homework 6 (Due April 11)
Homework 7 (Due April 18)
Homework 8 (Due April 25)
Homework 8 (Due May 7)
Homeworks will be assigned roughly every week. Homework assignments will be posted on the course webpage early in the week (hopefully by Monday, definitely by Tuesday) and will be due the following Tuesday. Expect there to be a homework assignment due every week except the first week of class, midterm week, and the week following Spring Recess (for a total of 9 assignments).
Format: Please type up your solutions. Please let the teaching staff know if this will be a problem. LaTeX is strongly preferred. Learning LaTex will require a learning curve, but will pay off in the long run. Once you are accustomed to LaTex, you will be able to typeset technical material such as equations very quickly.
Submission: Assignments will be due at 11:59pm on the due date of the assignment. Please submit your solutions digitally through Blackboard.
Collaboration Policy: You are encouraged to discuss homework assignments with other students in the class. However, students must write up solutions individually, and must not share their written solutions with classmates. Please identify your collaborators on your homework submissions.
Formalism: You must always show all of your work. Unless otherwise stated, any cryptosystem derived in the homework assignment must analyzed for both correctness and security. That is, you must prove both the correctness and security of the scheme. When asked to prove a statement (correctness/security or otherwise), the proof needs to be well written and rigorous. Your proofs do not need to be overly formal, but should not contain any logical gaps or errors. Any statements proved in lecture can be used in the solutions without proof, but any other statement should be proved as a part of the solution.
Extra Credit: There may be an occasional extra credit problem on the homework assignments. You are not required to attempt these problems, and will not be penalized for skipping them.
Flexibility: If you do not turn in an assignment, or turn in an assignment late, you will receive a zero for that assignment. However, your two lowest homework scores will automatically be dropped. You do not need to tell us which homework scores you would like to drop, and you do not need to let us know if you plan on not turning in an assignment — we will take care of the dropping for you. Any extra credit problems attempted in a dropped homework will still be considered in the overall grade.