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
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.
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
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 | 01/04 |
Introduction
Welcome / organizational details
What is this class about? Why study cryptography?
The Provable Security Angle
|
|
| 01/06 |
Introduction to Encryption
Symmetric Encryption
Attack types
Breaking monoalphaetic substitution
|
|
| 1 | 01/09 |
One-time Pads, Perfect Secrecy, and its Limitations
The one-time pad
Shannon and perfect secrecy
Limitations of perfect secrecy
Intro to computational hardness
|
|
| 01/11 |
Block Ciphers and Pseudorandom Permutations I
Definition of Block Ciphers
Definition of random permutations
|
|
| 01/13 |
Block ciphers and Pseudorandom Permutations II
Distinguishing Advantage
Definition of Pseudorandom Permutations
Design of AES
|
|
| 2 | 01/16 |
Martin Luther King Jr. Day
|
|
| 01/18 |
Symmetric Encryption: Definition
The design of AES
Insecurity of ECB
Introduction to semantic security
|
|
| 01/20 |
Symmmetric Encryption from PRFs I
Definition of IND-CPA security
Definition of PRFs
The PRF/PRP Switching Lemma and collision probabilities
|
|
| 3 | 01/23 |
Symmmetric Encryption from PRFs II
Security proof for the simple encryption scheme
Proofs via hybrid oracles
Basic reductions
|
|
| 01/25 |
Modes of Operation + Padding-Oracles Intro
CTR encryption
CBC encryption
Padding Schemes
|
|
| 01/27 |
Padding-Oracle Attacks
Fixing IND-CPA security for variable-length messages
Padding oracle attacks
Intro to ciphertext integrity
|
|
| 4 | 01/30 |
Hash Functions
Definition of collision-resistance
Applications of Hash Functions
The Merkle-Damgaard transform
|
|
| 02/01 |
Hash Functions & MACs
Security of Merkle-Damgaard
Seeded hash functions
Introduction to MACs
|
|
| 02/03 |
MACs
|
|
| 5 | 02/06 |
Authenticated Encryption
|
Take-home midterm posted (see edstem)
|
| 02/08 |
Computational Number Theory
Motivation of public-key cryptography
Groups
Modular arithmetic
|
|
| 02/10 |
Computational Number Theory II
Exponentiation
Cyclic groups
The discrete logarithm problem
|
Take-home midterm due, 11:59pm
|
| 6 | 02/13 |
Key Exchange
The Diffie-Hellman Protocol
The hardness of the DL problem
|
|
| 02/15 |
Elliptic Curves
|
|
| 02/17 |
Public-key Encryption and RSA
How to build public-key encryption from two-round Key Exchange
The ElGamal cryptosystem
Plain RSA
|
|
| 7 | 02/20 |
President's Day |
|
| 02/22 |
RSA & Factoring
RSA & Padding
IND-CCA security & OAEP
Hardness of factoring
|
|
| 02/24 |
Digital Signatures I
Handling large RSA decryption exponents
Fault & side-channel attacks
Introduciton to digital signatures
|
|
| 8 | 02/27 |
Digital Signatures II
|
|
| 03/01 |
Authenticatd Key-Exchange & TLS
|
|
| 03/03 |
Secure Messaging
Secure messaging desiderata
Symmetric Ratchet
Continuous Key-Agreement
|
|
| 9 | 03/06 |
Introduction to Cryptographic Protocols
Two-party computation and ideal functionalities
|
|
| 03/08 |
Two-party Computation I
Garbling an AND gate
Oblivious Transfer
|
|
| 03/10 |
Two-party Computation II
Yao's protocol & Garbled Circuits
DDH-based PSI protocol
|
|