---

General description

Cryptography provides important tools for ensuring the confidentiality and integrity of sensitive digital data. This course covers the design and application of important cryptographic objects, including basic cryptographic tools, such as encryption, message authentication, and digital signatures, as well as advanced cryptographic objects and protocols, such as zero-knowledge proofs, secure multi-party computation, and fully homomorphic encryption. For each cryptographic object, we formalize its security goal, show schemes that achieve the desired security, and study security attacks or security proofs that establish the insecurity or security of the scheme at hand. Through this course, we aim to give an overview of the discipline of cryptography, the proper usage and application of important cryptographic tools, and methodologies that modern cryptography offers for developing cryptographic solutions to natural security problems.

Pre-req: CSE 312 and CSE 332. The class will be self-contained. But students are expected to be ready to understand mathematical definitions and proofs, and write simple ones. Exposure to basic probability / algebra / number theory, and theory of computing is also expected. (Contact the instructor if in doubt.)

---

Resources

There is no mandatory textbook. Slides and reading materials will be posted throughout the class. However, the following are good references about basic cryptography. (Be aware that different textbooks make very different notational choices to explain the same concepts.)

• R. Pass and a. shelat. A Course in Cryptography (undergraduate level, focusing on theory)
• M. Rosulek. The Joy of Cryptography (undergraduate level, broader scope)
• O. Goldreich. The Foundations of Cryptography (a thorough and formal textbook on foundations.)
• J. Katz and Y. Lindell. Introduction to Modern Cryptography (a textbook, graduate levelmore advanced)
• D. Boneh and V. Shoup A Graduate Course in Applied Cryptography (a textbook, graduate level)
• M. Bellare and P. Rogaway's lecture notes. Introduction to Modern Cryptography (focus on practice-oriented provable security)

A good overview on secure multi-party computation (from an applier perspective) is available in this textbook (available for free!)

---

Policies

Accommodations: We will follow UW policies for disability accommodations and religious accommodations.
Academic conduct: Please also refer to UW policies on student conduct and academic integerity
Class attendence and Recordings: This class will take place in person, so are the sessions and office hours. Attendence is mandatory. The lectures will be recorded and recordings will be available on Canvas.
DRS accommodation: If you want DRS accommodations, you should email DRS as soon as possible. DRS will contact us directly to get these accomodations set up for you.
Homework policy:

• There will be six homework assignments, to be solved individually. Solutions are to be submitted over Gradescope. There will be homework 7 that will not be graded (and not counted towards final grade).
• With the exception of homework 1 (due to Martin Luther King Jr. Day), all homework will be posted on Friday before mid night and due one week later. See the schedule below for homework release and due dates.
• We strongly encourage you to type solutions up using LaTeX. Alternatively, you can use any other tool that properly displays equations (e.g., Word's equation editor).
• You must show your work; at a minimum 1-2 sentences per question, but ideally as much as you would need to explain to a fellow classmate who had not solved the problem before. Be concise. A correct answer with no work is worth nothing, less than a wrong answer with sufficient explanations explaining your reasoning.
• It is okay to discuss with other students in coming up with the homework solutions, but you must list all your collaborators at the top of each homework. Moreover, you have to write up your own solution and be able to explain your answer if asked to do so. If there are any doubts, we plan to do some spot checks in which we ask students to explain one of their solutions (or solve a slight variant of the problem they solved on the homework) in person.
• You have a total of six late days during the quarter, but can only use up to three late days on any one assignment. Please plan ahead, as we will not be willing to add any additional late days except in absolute, verifiable emergencies.
• Regrade requests are to be submitted within one week of the graded homework assignment being released.

Exams policy: All exams (midterm and final) will take place in the classroom. The final exam will be cumulative. The exams will be closed book, but you will be allowed to use a cheatsheet (more information will be provided at due time).

---

Grading

The following grading distribution may be slightly adjusted during the course of the quarter, according to the performance of the class.

• Homework (50%)
• Midterm (20%)
• Final (30%)

Exams grades will be curved upwards only. This means if the medium score is low, all scores will be shifted upwards, but if the medium score is high, no adjustment will be made. In other words, in the case of hard exams, the absolute scores do not matter.

---

Schedule

This is a tentative schedule meant to give an overview of the topics we are going to cover. The actual pace of the class may vary. See Edstem for updates

Wk	Date	Lecture contents	Homework Schedule
1	01/06	Introduction Welcome / organizational details What is this class about? Why study cryptography? The Provable Security Angle
	01/08	Introduction to Encryption Symmetric Encryption Attack types Breaking monoalphaetic substitution
	01/10	One-time Pads, Perfect Secrecy, and its Limitations The one-time pad Shannon and perfect secrecy Limitations of perfect secrecy Intro to computational hardness
2	01/13	Block Ciphers and Pseudorandom Permutations I Definition of Block Ciphers Definition of random permutations
	01/15	Block ciphers and Pseudorandom Permutations II Distinguishing Advantage Definition of Pseudorandom Permutations Design of AES	HW1 out
	01/17	Symmetric Encryption: Definition The design of AES Insecurity of ECB Introduction to semantic security
3	01/20	Martin Luther King Jr. Day
	01/22	Symmmetric Encryption from PRFs I Definition of IND-CPA security Definition of PRFs The PRF/PRP Switching Lemma and collision probabilities
	01/24	Symmmetric Encryption from PRFs II Security proof for the simple encryption scheme Proofs via hybrid oracles Basic reductions	HW1 due, HW2 out
4	01/27	Modes of Operation + Padding-Oracles Intro CTR encryption CBC encryption Padding Schemes
	01/29	Padding-Oracle Attacks Fixing IND-CPA security for variable-length messages Padding oracle attacks Intro to ciphertext integrity
	01/31	Hash Functions Definition of collision-resistance Applications of Hash Functions The Merkle-Damgaard transform	HW2 due
5	02/03	Hash Functions & MACs Security of Merkle-Damgaard Seeded hash functions Introduction to MACs
	02/05	MACs
	02/07	In-Class Midterm	HW3 out
6	02/10	Authenticated Encryption
	02/12	Computational Number Theory Motivation of public-key cryptography Groups Modular arithmetic
	02/14	Computational Number Theory II Exponentiation Cyclic groups The discrete logarithm problem	HW3 due, HW4 out
7	02/17	Key Exchange The Diffie-Hellman Protocol The hardness of the DL problem
	02/19	Elliptic Curves
	02/21	Public-key Encryption and RSA How to build public-key encryption from two-round Key Exchange The ElGamal cryptosystem Plain RSA	HW4 due, HW5 out
8	02/24	RSA & Factoring RSA & Padding IND-CCA security & OAEP Hardness of factoring
	02/26	Digital Signatures I Handling large RSA decryption exponents Fault & side-channel attacks Introduciton to digital signatures
	02/28	Digital Signatures II	HW5 due, HW6 out
9	03/03	Authenticatd Key-Exchange & TLS
	03/05	Secure Messaging Secure messaging desiderata Symmetric Ratchet Continuous Key-Agreement
	03/07	Introduction to Cryptographic Protocols Two-party computation and ideal functionalities	HW6 due, HW7 out
10	03/10	Two-party Computation I Garbling an AND gate Oblivious Transfer
	03/12	Two-party Computation II Yao's protocol & Garbled Circuits DDH-based PSI protocol
	03/14	Secret-Sharing and Multi-Party Computation Problem statement Secret sharing Protocol for addition A general solution