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 zeroknowledge proofs, secure multiparty 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.
Prereq: CSE 312 and CSE 332. The class will be selfcontained. 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 multiparty 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 COVID19 situation during the course of the quarter
 Homework (60%)
 Midterm (15%, takehome)
 Final (25%, takehome)
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 
Onetime Pads, Perfect Secrecy, and its Limitations
 The onetime 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 INDCPA 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 + PaddingOracles Intro
 CTR encryption
 CBC encryption
 Padding Schemes


 01/27 
PaddingOracle Attacks
 Fixing INDCPA security for variablelength messages
 Padding oracle attacks
 Intro to ciphertext integrity


4  01/30 
Hash Functions
 Definition of collisionresistance
 Applications of Hash Functions
 The MerkleDamgaard transform


 02/01 
Hash Functions & MACs
 Security of MerkleDamgaard
 Seeded hash functions
 Introduction to MACs


 02/03 
MACs


5  02/06 
Authenticated Encryption

 Takehome midterm posted (see edstem)

 02/08 
Computational Number Theory
 Motivation of publickey cryptography
 Groups
 Modular arithmetic


 02/10 
Computational Number Theory II
 Exponentiation
 Cyclic groups
 The discrete logarithm problem

 Takehome midterm due, 11:59pm

6  02/13 
Key Exchange
 The DiffieHellman Protocol
 The hardness of the DL problem


 02/15 
Elliptic Curves


 02/17 
Publickey Encryption and RSA
 How to build publickey encryption from tworound Key Exchange
 The ElGamal cryptosystem
 Plain RSA


7  02/20 
President's Day 

 02/22 
RSA & Factoring
 RSA & Padding
 INDCCA security & OAEP
 Hardness of factoring


 02/24 
Digital Signatures I
 Handling large RSA decryption exponents
 Fault & sidechannel attacks
 Introduciton to digital signatures


8  02/27 
Digital Signatures II


 03/01 
Authenticatd KeyExchange & TLS


 03/03 
Secure Messaging
 Secure messaging desiderata
 Symmetric Ratchet
 Continuous KeyAgreement


9  03/06 
Introduction to Cryptographic Protocols
 Twoparty computation and ideal functionalities


 03/08 
Twoparty Computation I
 Garbling an AND gate
 Oblivious Transfer


 03/10 
Twoparty Computation II
 Yao's protocol & Garbled Circuits
 DDHbased PSI protocol

