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


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


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.) A good overview on secure multi-party computation (from an applier perspective) is available in this textbook (available for free!)


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


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.

WkDate Lecture contents Reading & Homework
0 09/29 Introduction
  • Welcome / organizational details
  • What is this class about? Why study cryptography?
  • The Provable Security Angle
10/1 Introduction to Encryption
  • Symmetric Encryption
  • Attack types
  • Breaking monoalphaetic substitution
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
10/6 Block Ciphers and Pseudorandom Permutations I
  • Definition of Block Ciphers
  • Definition of random permutations
10/8 Block ciphers and Pseudorandom Permutations II
  • Distinguishing Advantage
  • Definition of Pseudorandom Permutations
  • Design of AES
2 10/11 Symmetric Encryption: Definition
  • The design of AES
  • Insecurity of ECB
  • Introduction to semantic security
10/13 Symmmetric Encryption from PRFs I
  • Definition of IND-CPA security
  • Definition of PRFs
  • The PRF/PRP Switching Lemma and collision probabilities
10/15 Symmmetric Encryption from PRFs II
  • Security proof for the simple encryption scheme
  • Proofs via hybrid oracles
  • Basic reductions
3 10/18 Modes of Operation + Padding-Oracles Intro
  • CTR encryption
  • CBC encryption
  • Padding Schemes
  • 10/20 Padding-Oracle Attacks
    • Fixing IND-CPA security for variable-length messages
    • Padding oracle attacks
    • Intro to ciphertext integrity
    10/22 Hash Functions
    • Definition of collision-resistance
    • Applications of Hash Functions
    • The Merkle-Damgaard transform
    4 10/25 Hash Functions & MACs
    • Security of Merkle-Damgaard
    • Seeded hash functions
    • Introduction to MACs
    10/27 MACs
    10/29 Authenticated Encryption
    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
    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
    11/10 Elliptic Curves
    11/12 Public-key Encryption and RSA
    • How to build public-key encryption from two-round Key Exchange
    • The ElGamal cryptosystem
    • Plain RSA
    7 11/15 RSA & Factoring
    • RSA & Padding
    • IND-CCA security & OAEP
    • Hardness of factoring
    11/17 Digital Signatures I
    • Handling large RSA decryption exponents
    • Fault & side-channel attacks
    • Introduciton to digital signatures
    11/19 Digital Signatures II
    8 11/22 Authenticatd Key-Exchange & TLS
    11/24 Secure Messaging
    • Secure messaging desiderata
    • Symmetric Ratchet
    • Continuous Key-Agreement
    11/26 Thanksgiving (no class)
    9 11/29 Introduction to Cryptographic Protocols
    • Two-party computation and ideal functionalities
    12/1 Two-party Computation I
    • Garbling an AND gate
    • Oblivious Transfer
    12/3 Two-party Computation II
    • Yao's protocol & Garbled Circuits
    • DDH-based PSI protocol
    10 12/6 Secret-Sharing and Multi-Party Computation
    • Problem statement
    • Secret sharing
    • Protocol for addition
    • A general solution
    12/8 Ethics, Policy & Cryptography
    12/10 Take-home final: Review & Discussion