COS 433 - Cryptography (Spring 2020)
Course Information
| Instructor: | Mark Zhandry ( ) |
| Office Hours: Fridays 11am (Zoom) | |
| TA: | Ben Kuykendall |
| Office Hours: Mondays 3pm (Zoom) | |
| TA: | Jiaxin Guan |
| Office Hours: Wednesdays 1pm (Zoom) | |
| Lecture: | TuTh 11:00am - 12:20pm, Zoom |
| Grading: | 40% for roughly weekly homeworks, 30% Projects, 30% take-home final |
| Piazza: | https://piazza.com/class/k62c87yjhgl51n |
| 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 - Tu, 2/4 | Course introduction, Pre-modern Crypto Part I | 1.3 | [1] |
| 2 - Th, 2/6 | Pre-modern Crypto Part II | 1.4-2.2 | [2] |
| 3 - Tu, 2/11 | Definitions in Cryptography, Randomized Encryption | [3] | |
| 4 - Th, 2/13 | Limitations of Information-Theoretic Security, Stream Ciphers, PRGs, and Computational Assumptions | 2.3-3.3 | [4] |
| 5 - Tu, 2/18 | Constructing PRGs | 6.1 | [5] |
| 6 - Th, 2/20 | CPA security and PRFs | 3.4-3.5 | [6] |
| 7 - Tu, 2/25 | PRPs, Block Ciphers, Modes of Operation | 3.6, 6.2 | [7] |
| 8 - Th, 2/27 | Constructing Block Ciphers | 6.2 | [8] |
| 9 - Tu, 3/3 | Attacks on Block Ciphers | 6.2 | [9] |
| 10 - Th, 3/5 | Message Integrity, MACs | 4.1-4.4, 4.6 | [10] |
| 11 - Tu, 3/10 | Message Integrity, MACs, continued | 4.1-4.4, 4.6 | [11] |
| 12 - Th, 3/12 | Class Cancelled | ||
| M, 3/20 | No Class - Spring Break | ||
| W, 3/22 | |||
| 13 - Tu, 3/24 | Authenticated Encryption, CCA Security | 4.5 | [12] |
| 14 - Th, 3/26 | Collision Resistant Hashing | 5.1-5.4, 6.3 | [13] |
| 15 - Tu, 3/31 | Commitment Schemes | [14] | |
| 16 - Th, 4/2 | Number-theoretic constructions of symmetric primitives | 8.3-8.4 | [15] |
| 17 - Tu, 4/7 | Number-theoretic constructions of symmetric primitives | 8.3-8.4 | [16] |
| 18 - Th, 4/9 | Public Key Encryption | 11.1-11.4 | [17] |
| 19 - Tu, 4/14 | RSA, Trapdoor Permutations | 11.5, 13.1 | [18] |
| 20 - Th, 4/16 | Digital Signatures | 12.1-12.4 | [19] |
| 21 - Tu, 4/21 | Digital Signatures, Identification Protocols | 12.5 | [20] |
| 22 - Th, 4/23 | Identification Protocols | 12.5 | [21] |
| 23 - Tu, 4/28 | Zero Knowledge | [22] | |
| 24 - Th, 4/30 | Wrap up | [23] | |
Handouts
Basic Number TheoryHomework Assignments
Homework 7: [HW7]. Due Sunday May 3, 11:59pm. [Submission Link]Homework 6: [HW6]. Due Sunday April 26, 11:59pm. [Submission Link]
Homework 5: [HW5]. Due Thursday April 9, 11:59pm. [Submission Link]
Homework 4: [HW4]. Due Thursday April 2, 11:59pm. [Submission Link]
Homework 3: [HW3]. Due Thursday March 5, 11:59pm. [Submission Link]
Homework 2: [HW2]. Due Thursday February 27, 11:59pm. [Submission Link]
Homework 1: [HW1]. Due Thursday February 20, 11:59pm. [Submission Link]
Homework 0: Due Friday February 7, 11:59pm. Please fill out the following poll to indicate your availability for office hours. Please fill out your general availability for days of the week/times during the Spring semester. Once everyone has filled out the poll, the teaching staff will decide on office hours.
https://www.when2meet.com/?8678874-HzQIA
Homework Instructions:
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 Thursday. Expect there to be a homework assignment due every week except the first two weeks of class, midterm week, and the week following Spring Recess (for a total of 8 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. 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.
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: You will be given four late days for assignments for the semester. These late days can be used in 24-hour increments; any number of late days can be used on a given assignment. Late days will be assessed automatically. No additional late days will be given, except for medical or personal emergencies; such emergencies must be documented in a note from a Dean or Director of Studies.
Latex source files for first homework:
HW1.tex
template.tex
Take Home Final
TBAOld exams: Spring 2017 Spring 2018
Projects
Project 3/Homework 8: Instructions: [PR3]. Due Date: May 12, 11:59pm. [Submission Link]Project 2: Instructions: [PR2]. Hash function example inputs: [examples.txt]. Due Date: Sunday, April 19, 11:59pm. [Submission Link]
Project 1: Instructions: [PR1]. Ciphertexts: [ctxts]. Due Date: Thursday, March 12, 11:59pm. [Submission Link]
Grading
h = min(total homework points, 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.