General information

  • Topics: Basic cryptographic primitives (block ciphers, secret- and public-key encryption, authenticated encryption, message authentication, signatures, ...), cryptographic protocols (e.g. TLS), attack vectors (padding-oracle attacks, side-channel attacks, etc). Also, advanced cryptographic techniques (zero-knowledge proofs, multi-party computation,...).
    The class will adopt rigorous security definitions and statements, but mostly replace proofs with attack-driven intuition.
  • Prerequisites: No formal prerequisites, except for basic mathematical proficiency as expected in an undergraduate CS program, as well as a certain affinity to rigorous thinking. Basic programming skills (we will mostly use Python).

Team

Instructor: Huijia (Rachel) Lin, rachel(at)cs(dot)washington(dot)edu

Teaching assistant

  • Champ Chairattana-Apirom (rchairat@cs)
  • Sela Navot (senavot@cs)

Weekly schedule

  • Class time and location
    Monday 6:30-9:20pm, CSE2 G20 (with live streaming on Microsoft campus)
  • Class Recording Lectures are recorded and recordings are available here
  • Office hours
    Rachel: Tues 5:00-6:00pm on Zoom or by appointment
    Sela: Mons: 5:15-6:15pm in person
    Champ: Weds 5:15-6:15pm on Zoom
    Office hour starts in the second week. Zoom links are posted on Edstem

Resources

No mandatory textbook. Slides will be made available (password protected).

The following are lecture notes/textbooks on cryptography (all but one free), which (often) adopt a more formal approach than the one from this class.

Interaction / Q&A

We are going to use edstem for class discussion. Instructions will be provided.

Grading

  • Homework: There will be 6 problem sets distributed over the quarter. Problem sets are generally posted online on Tuesdays, by 11:59pm PST, and are due on Thursdays, 11:59pm PST, the following week. Homework will be graded and you are required to hand in your own solution for each homework. (Refer to the "Academic Integrity" paragraph below for further details.) The lowest grade among the 6 homework will be dropped. You are allowed 5 late days overall throughout the quarter.
    Homework submissions will be online via Gradescope (instructions will be provided soon).
  • Project: An important component of this class will be a project, to be undertaken by teams of two students. (Exceptions can be made but are not the norm.) The final outcome of the project is a report (we will likely dispense with presentations, due to the projected high number of students). Examples of projects include (but are not limited to):
    • Reading a research paper and/or a cryptographic standard/RFC (either existing, or a current proposal), and writing a summary.
    • Studying a real-world application or implementation of cryptography (either a well-known one, or something specific to your personal experience) and documenting it (or formalizing the underlying threat model).
    • Some cryptography-specific implementation problem.
    • Anything else really, just let your creativity flow.
    A project proposal (0.5-1 pages) describing the planned work and the two members of each time is due on Monday, May 1st. Early submissions are welcome and encouraged. The final project is due then on Monday, June 5th, 11:59pm.
  • Final grade: The final grade will be distributed as follows: Homework (60%), project (40%). The lowest homework score will be dropped. Participation (in class and online) will be taken into account for partial bonus credit in borderline cases.
  • Academic Integrity: Homework assignments are meant to be solved individually, whereas collaboration with a team-mate is required for the project component of the class. Please refer to the Allen School's Academic Misconduct webpage for a detailed description of what is allowable and what is not.
  • Religious Accommodation Policy: See here for the current policy.

Schedule and Homework

The following is a tentative schedule, and is intended to give a rough idea about what I hope to cover in the class and in which order. There will be (slight) shifts depending on the pace of the class.

WeekDate Lecture contentsHomework and Project
1 2023-03-27 Introduction
  • Organizational details.
  • Introduction: What is cryptography?
Introduction to symmetric encryption
  • Historic ciphers
  • Attack models
  • Breaking monoalphabetic substitution
  • Definition of block ciphers
2 2023-04-03 Block Ciphers
  • Definition (reminder)
  • ECB mode and its insecurity
  • Pseudorandom Functions
  • The Structure of AES
Modes of operation
  • The structure of AES
  • CTR/CBC modes
  • IND-CPA security for symmetric encryption
  • Stream ciphers: Constructions from block ciphers & ad-hoc designs
  • HW1 out on Tuesday
3 2023-04-10 Wrapping Up Encryption
  • Breaking RC4
  • Padding-oracle attacks
Integrity
  • Hash functions: Basic properties (collision resistance, second preimage resistance, etc)
  • The Merkle-Damg√•rd and Sponge constructions
  • Merkle Trees
  • Message-authentication codes (MACs)
  • MAC Constructions: Keying hash functions (HMAC) and CBC
  • HW2 out on Tuesday.
  • HW1 due on Thursday
4 2023-04-17 Authenticated Encryption
  • Plaintext and ciphertext integrity
  • Generic composition: Secure and insecure solutions
  • AEAD and GCM
  • Nonce repetitions, nonce-misuse resistance, picking nonces
Public-key crypto foundations
  • Modular arithmetic
  • Cyclic groups
  • The Discrete Logarithm problem
  • Elliptic curves
  • HW3 out on Tuesday.
  • HW2 due on Thursday
5 2023-04-24 Public-key Cryptography
  • Diffie-Hellman Key-Exchange
  • Hardness of the discrete logarithm problem
RSA Encryption
  • Plain RSA
  • PKCS#1 encryption
  • RSA-OAEP and chosen-ciphertext security
  • Basic attacks and factoring
Digital Signatures
  • Functionality
  • RSA & Schnorr signatures
  • HW4 out on Tuesday.
  • HW3 due on Thursday
6 2023-05-01 Certificates, PKIs, and authenticated key exchange
  • Certificates and public-key infrastructures
Authenticated Key Exchange (AKE)
  • Generic constructions: One-sided and two-sided AKE
  • Forward security
  • Diffie-Hellman AKE and TLS 1.3 handshake
  • Attacks against older TLS versions: FREAK and LogJam
  • HW5 out on Tuesday
  • HW4 due on Thursday
7 2023-05-08 Identification protocols
  • Password-based identification: Salting, iteration,
  • Memory-hard functions
  • One-time passwords
  • Challenge-response protocols
Random-number generation
  • Bad RNGs (Mersenne Twister)
  • RNG security: Pseudorandomness, forward-security, post-comrpomise security
  • Hash-based RNG design
  • RNG attacks
  • HW 5 due on Thursday
8 2023-05-15 Case study: Secure Messaging
  • The Double-Ratchet Protocol
Multi-party computation
  • Two-party computation
  • Oblivious transfer
  • Garbled Circuits and Yao's protocol
  • HW6 out on Tuesday
9 2023-05-22 Multi-party computation
  • Garbled Circuits and Yao's protocol
  • Secret sharing and multi-party computation
Zero-knowldge proofs
  • HW 6 due on Thursday
10 2020-05-29 Memorial Day