---

Important: COVID-19 measures

This class will take place in person during an ongoing pandemic. Needless to say, this will require a high degree of flexibility (and compliance) on everyone's part to succeed and to ensure everyone's safety. The following are some important remarks - read them carefully:

• If you have symptoms, stay home! Follow all appropriate guidelines for testing and isolating.
• Masking during class is mandatory. Please refer to UW's COVID-19 face cover policy for details.
• Classes will be automatically recorded and made available on Panopto, as soon as technically feasible after class.
• We plan to hold some of the office hours in person, but we may adjust the policy as the quarter progresses depending on preferences and demand. Stay tuned for more information. We will in particular introduce a policy to prevent overcrowding of physical spaces.
• We are not planning for in-person exams. Both the midterm and final exams will be in take home format, to be solved individually.
• There will be no sections or office hours during the first week of instruction ("Week 0") - this will give us the necessary time to roll out safe protocols.
• Attend your assigned section to avoid overcrowding of rooms.
• If you want DRS accommodations (e.g., because you have a condition that would make it unsafe or undesirable to be indoor in a classroom), you should email DRS as soon as possible. DRS will contact us directly to get these accomodations set up for you.

You should expect that many policies will be subject to change. Part of this will be about refining existing processes, but we may also be subject to new regulations, and the conditions of the pandemic may force us to be back online. Be flexible and proactive. We may need to cancel classes on short notice, or take other extrardinary measures in the case the staff or some of you are going to become ill. Make sure to subscribe to edstem notifications so that you can be alerted quickly about possible changes.

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.)

---

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

---

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!)

---

Grading

The following grading distribution may be slightly changed to accommmodate for changes of the COVID-19 situation during the course of the quarter

• Homework (60%)
• Midterm (15%, take-home)
• Final (25%, take-home)

---

Schedule

This is a tentative schedule meant to give an overview of the topics we are going to cover. It will be expanded as we proceed through the quarter.

Wk	Date	Lecture contents	Reading & Homework
0	09/29	Introduction Welcome / organizational details What is this class about? Why study cryptography? The Provable Security Angle	[Slides]
	10/1	Introduction to Encryption Symmetric Encryption Attack types Breaking monoalphaetic substitution	[Slides]
1	10/4	One-time Pads, Perfect Secrecy, and its Limitations The one-time pad Shannon and perfect secrecy Limitations of perfect secrecy Intro to computational hardness	[Slides]
	10/6	Block Ciphers and Pseudorandom Permutations I Definition of Block Ciphers Definition of random permutations	[Slides] [Homework 1] [Section 1] [Solution]
	10/8	Block ciphers and Pseudorandom Permutations II Distinguishing Advantage Definition of Pseudorandom Permutations Design of AES	[Slides] [Annotated]
2	10/11	Symmetric Encryption: Definition The design of AES Insecurity of ECB Introduction to semantic security	[Slides] [Annotated]
	10/13	Symmmetric Encryption from PRFs I Definition of IND-CPA security Definition of PRFs The PRF/PRP Switching Lemma and collision probabilities	[Slides] [Annotated] [Homework 2] [Section 2] [Solution]
	10/15	Symmmetric Encryption from PRFs II Security proof for the simple encryption scheme Proofs via hybrid oracles Basic reductions	[Slides] [Annotated] HW1 due
3	10/18	Modes of Operation + Padding-Oracles Intro CTR encryption CBC encryption Padding Schemes	[Slides] [Annotated]
	10/20	Padding-Oracle Attacks Fixing IND-CPA security for variable-length messages Padding oracle attacks Intro to ciphertext integrity	[Slides] [Annotated] [Homework 3] [oracle.py] [Sample 1] [Sample 2] [Section 3] [Solution]
	10/22	Hash Functions Definition of collision-resistance Applications of Hash Functions The Merkle-Damgaard transform	[Slides] [Annotated] HW2 due (deadline moved to Sunday 10/24!)
4	10/25	Hash Functions & MACs Security of Merkle-Damgaard Seeded hash functions Introduction to MACs	[Slides] [Annotated]
	10/27	MACs	[Slides] [Section 4] [Solution]
	10/29	Authenticated Encryption	[Slides] HW3 due
5	11/1	Take-home midterm: Review & Discussion Mostly: review on security reductions	[Slides] (no annotations, but see panopto recording for work at the board!) Take-home midterm posted (see edstem)
	11/3	Computational Number Theory Motivation of public-key cryptography Groups Modular arithmetic	[Slides] [Section 5] [Solution]
	11/5	Computational Number Theory II Exponentiation Cyclic groups The discrete logarithm problem	[Slides] Take-home midterm due, 11:59pm
6	11/8	Key Exchange The Diffie-Hellman Protocol The hardness of the DL problem	[Slides]
	11/10	Elliptic Curves	[Slides] [Homework 4] [Section 6] [Solution]
	11/12	Public-key Encryption and RSA How to build public-key encryption from two-round Key Exchange The ElGamal cryptosystem Plain RSA	[Slides]
7	11/15	RSA & Factoring RSA & Padding IND-CCA security & OAEP Hardness of factoring	[Slides]
	11/17	Digital Signatures I Handling large RSA decryption exponents Fault & side-channel attacks Introduciton to digital signatures	[Slides] [Homework 5] [Section 7] [Soution]
	11/19	Digital Signatures II	[Slides] HW4 due
8	11/22	Authenticatd Key-Exchange & TLS	[Slides]
	11/24	Secure Messaging Secure messaging desiderata Symmetric Ratchet Continuous Key-Agreement	[Slides] [Homework 6]
	11/26	Thanksgiving (no class)
9	11/29	Introduction to Cryptographic Protocols Two-party computation and ideal functionalities	HW5 due [Slides]
	12/1	Two-party Computation I Garbling an AND gate Oblivious Transfer	[Slides] [Section 8] [Soution]
	12/3	Two-party Computation II Yao's protocol & Garbled Circuits DDH-based PSI protocol	[Slides]
10	12/6	Secret-Sharing and Multi-Party Computation Problem statement Secret sharing Protocol for addition A general solution	[Slides] HW6 due
	12/8	Ethics, Policy & Cryptography	[Slides] [Section 9] Phillip Rogaway. The Moral Character of Cryptographic Work
	12/10	Take-home final: Review & Discussion