COS 433 - Cryptography (Fall 2020)
Course Information
| Instructor: | Mark Zhandry ( ) |
| Office Hours: Monday 10am (EST) | |
| TA: | Udaya Gai |
| Office Hours: Tuesday 7-8pm (EST) | |
| TA: | Anunay Kulshrestha |
| Office Hours: Wednesday 1:30-2:30pm (EST) | |
| Lecture: | TuTh 11:00am - 12:20pm, Zoom |
| Grading: | 40% Homeworks, 30% Projects, 30% take-home final |
| 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. The course projects will involve programming, but no specific programming language is required.
Tentative Schedule (subject to change)
| Lecture | Topic | KL Section | Notes | ||
| 1 - Tu, 9/1 | Course introduction, Pre-modern Crypto Part I | 1.3 | [1] | ||
| 2 - Th, 9/3 | Pre-modern Crypto Part II | 1.4-2.2 | [2] | ||
| 3 - Tu, 9/8 | Definitions in Cryptography, Randomized Encryption | [3] | |||
| 4 - Th, 9/10 | Limitations of Information-Theoretic Security, Stream Ciphers, PRGs, and Computational Assumptions | 2.3-3.3 | [4] | ||
| 5 - Tu, 9/15 | Constructing PRGs | 6.1 | [5] | ||
| 6 - Th, 9/17 | CPA security and PRFs | 3.4-3.5 | [6] | ||
| 7 - Tu, 9/22 | PRPs, Block Ciphers, Modes of Operation | 3.6, 6.2 | [7] | ||
| 8 - Th, 9/24 | Constructing Block Ciphers | 6.2 | [8] | ||
| 9 - Tu, 9/29 | Attacks on Block Ciphers | 6.2 | [9] | ||
| 10 - Th, 10/1 | Message Integrity, MACs | 4.1-4.4, 4.6 | [10] | ||
| 11 - Tu, 10/6 | Authenticated Encryption, CCA Security | 4.5 | [11] | ||
| 12 - Th, 10/8 | Collision Resistant Hashing | 5.1-5.4, 6.3 | [12] | ||
| Tu, 10/13 | No Class - Fall Break | ||||
| 13 - Th, 10/15 | Commitment Schemes | [13] | |||
| 14 - Tu, 10/20 | Number-theoretic constructions of symmetric primitives | 8.3-8.4 | [14] | ||
| 15 - Th, 10/22 | Number-theoretic constructions of symmetric primitives | 8.3-8.4 | [15] | ||
| 16 - Tu, 10/27 | Relationships between Symmetric Primitives | 7.2 | [16] | ||
| 17 - Th, 10/29 | Diffie Hellman Key Exchange | 10.3 | [17] | ||
| 18 - Tu, 11/3 | Public Key Encryption | 11.1-11.4 | [18] | ||
| 19 - Th, 11/5 | RSA, Trapdoor Permutations | 11.5, 13.1 | [19] | ||
| 20 - Tu, 11/10 | Digital Signatures | 12.1-12.4 | [20] | ||
| 21 - Th, 11/12 | Digital Signatures, Identification Protocols | 12.5 | [21] | ||
| 22 - Tu, 11/17 | Identification Protocols | 12.5 | [22] | ||
| Th, 11/19 | Class Cancelled | ||||
| 24 - Tu, 11/24 | Wrap up | [23] | |||
Handouts
Basic Number TheoryHomework Assignments
Homework 6. Due November 24.Homework 5. Due November 10.
Homework 4. Due October 27.
Homework 3. Due October 20.
Homework 2. Due September 29.
Homework 1. Due September 15.
Homework Instructions:
Homeworks will be assigned roughly every two weeks, with six homework assignments in total.Format: Typed solutions are strongly preferred. For hand-written submissions, please make sure the writing is legible. If we can't read it, we can't grade it, and we will not be entertaining regrade requests for illegible solutions. We encourage typesetting your solutions in LaTeX. 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 Anywhere on Earth on the due date of the assignment. The due date will typically be Tuesday. Submission instructions TBA.
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.
Internet Policy: If you find an answer to an exercise online, you may base your solution on what you found, but the solutions must be clearly in your own words in order to demonstrate your understanding of the answer. Additionally, please cite any source. On the other hand, you may not post homework questions hoping for other people to solve them.
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. Extra credit will be applied only after deciding the curve.
Flexibility: We will automatically drop your single lowest homework score. Additionally, we will accept any homework assignment up to 48 hours late. There will be no penalty for turning in homeworks late as long as they are received within the 48 hour window. However, to encourage you to turn in assignments on time, we will give 2 bonus points for each homework assignment that you submit on time. After the 48 hour grace period, we will not be able to accept any submissions. This is so that we can start grading promptly once the 48 hour window has closed, in order to give feedback in a timely fashion.
Latex source files for first homework:
HW1.tex
template.tex
Projects
Project 2: [Instructions], Hash function example inputs: [examples.txt]. Due Dec 5. Project 1: [Instructions], [files]. Due October 6. There will be two projects. Projects will follow the same 48 hour grace period as homeworks (including bonus points). You may not drop a project.Take Home Final
TBAOld exams: Spring 2017 Spring 2018 Spring 2020
Grading
h = total homework points (out of 400)p = total project points (out of 300)
f = final points (out of 300)
Numerical grade = (h+p+f)/10
There is no set curve or grading scale for the course (so for example a 90% may or may not end up being an A). However, expect the grade distribution to be roughly consistent with upper-level COS courses.