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


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


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.

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
10/15 Symmmetric Encryption from PRFs II
3 10/18 Modes of Operatin + Padding-Oracles Intro
10/20 Hash functions II + Message-authentication Codes I
  • HW3 posted
10/22 Message-authentication Codes II
  • HW2 due
4 10/25 Breaking encryption: Padding-oracle attacks
10/27 Authenticated Encryption I
10/29 Authenticated Encryption II
  • HW3 due
5 11/1 Take-home midterm: Review & Discussion
  • Take-home midterm posted
11/3 Computational Number Theory
11/5 Diffie-Hellman Key Exchange
  • Take-home midterm due, 11:59pm
6 11/8 The Discrete Logarithm Problem
11/10 Elliptic Curves
  • HW4 posted
11/12 Public-key Encryption and RSA
7 11/15 RSA & Factoring
11/17 Digital Signatures I
  • HW5 posted
11/19 Digital Signatures II
  • HW4 due
8 11/22 Post-Quantum Cryptography & Learning With Errors
11/24
  • HW6 posted
11/26 Thanksgiving (no class)
9 11/29 Fully-Homomorphic Encryption
  • HW5 due
12/1 Two-party Computation I
12/3 Two-party Computation II
10 12/6 Secret-Sharing and Multi-Party Computation
  • HW6 due
12/8 Ethics & Cryptography
12/10 Take-home final: Review & Discussion