CSE 526: Introduction to Gems in Cryptography (Winter 2022)

General Information

Instructor: Huijia (Rachel) Lin, rachel(at)cs

TA: hanjul (at) cs

Time and location:

  • Class: Monday/Wednesday 10:00am-11:20pm, CSE2 271

Office hours:

  • Rachel Lin: Monday 4:00pm-5:00pm, CSE 652 and on Zoom
  • Hanjun Li: Tuesday 4:00pm-5:00pm, Allen 5th Floor Breakout and on Zoom

Discussion: We are going to use Edstem Board. Notes and reading material will also be posted at Edstem.

Homework: Homework will be handled using Gradescope (UWnetid protected).


Cryptography provides important tools for ensuring the confidentiality and integrity of sensitive digital data. Core cryptographic tools, such as encryption, message authentication codes, and hash functions, are widely deployed to protect data that is communicated across the Internet and that is used in every domain including finance, commerce, healthcare, infrastructure, and national security. Our entire modern way of life would collapse without these tools. As society adapts to enjoy new computing technologies (e.g., artificial intelligence, precision health, and smart devices) that reap the benefits of learning from private data, the conflict between privacy and utility is becoming increasingly contentious. It is thus imperative to develop tools that enable utilizing the data while protecting them simulatneously. To this end, magical cryptographic objects, such as zero-knowledge proofs, secure multi-party computation, fully homomorphic encryption, and program obfuscation have emerged.

This course gives an introduction to these gems in cryptography, as well as the the mathematical frameworks and methodologies that modern cryptography has developed over the past decades. The first half of the class will focus on core cryptographic tools (e.g., encryption, message authentication, hash functions, etc.) while the second half will introduce more powerful objects (e.g., fully homomorphic encryption, program obfuscation). In order to cover all these gems, we will put more emphasis on ideas, and perfer simple constructions for illustrating a notion, over the most efficient and optimized versions.

Prerequisite: Most importantly, students should be ready to read and write (and even enjoy!) mathematical definitions and proofs. We will assume basic knowledge of discrete probability (e.g., events, random variables, expectations, conditional probability, Chernoff, union bound) / basic algebra (e.g., modular arithmetics, matrixes, vectors, some group theory that can be picked up along the way) / number theory (e.g., primes, greatest common divisor), and theory of computing (e.g., the big-Oh notation, running time analysis, NP reduction). If a student is mathemathically mature, most of these prerequisite can be picked up along the way.


There is no mandatory textbook. Notes and reading material will be posted on Edstem. Following is a list of great resources to reference to.


There will be four homework, each of which accounts for 10% of points. Students are responsible for scribing notes for one or two class, which together with attendence, in person or virtually, counts as 10% of the points. The remaining 50% of the points will be assigned to either a take-home final exam, or a project, by your choice. Homework can be solved in teams of 2, and each team has a total of 6 late days for homework submission, which can be used in any fashion.

On-going Pandemic:

We are having this class during an on-going pandemic. If any student feels sick, please do not hesitate to attend the class virtually, or skip the class. If any student has any circumstancs, we will accommodate flexibly. Please reach out the instructor and the TA directly. We are here to learn and to support each other.

Syllabus (Tentative)

1 Jan 3rd, 5th
  • Introduction
    • Secret Key Encryption
    • Perfect Secrecy and One-Time Pad
    • Computational Security
    • One-Way Functions
    2 Jan 10th, 12th
  • Candidate One-Way Functions
    • Factoring
    • RSA (trapdoor door permutation)
    • Discrete Logarithm, Decisional Diffie Hellman (Key Exchange)
  • Computational Indistinguishability
    • Definition of Computational Indistinguishability
    • Pseudo-Random Generator (PRG)
    • Output expansion of PRG and Hybrid argument
    • Algebraic construction of PRG
    Homework 1 out on Thursday
    3 Jan 17th, 19th
  • No Lecture on Jan 17th, Happy MLK day!
  • Pseudo-Random Function
    • Definition of Pseudo-Random Function (PRF)
    • The Goldreich-Goldwasser-Micali PRF construction from PRG
    • Algebriac Construction of PRF
    4 Jan 24th, 26th
  • Secret Key Encryption
    • IND-CPA security
    • Construction from PRF
  • Public Key Encryption
    • Construction from Trapdoor Permutation
    • Construction from Key Exchange
  • Homework 1 due on Wednesday

    Homework 2 out on Thursday

    5 Jan 31st, Feb 2nd
  • Message Authentication Code
    • Unforgeability
    • MAC from PRF
  • Hash Function
    • Hash function from Discrete Logarithm
    • Merkel Damgard domain extension
    • Random Oracle Model
  • Digital Signature
    • Signature from TDP
    • Full Domain Hash
    • Domain Extension
    6 Feb 7th, 9th
  • Signatures II
  • Lattice Based Cryptography I
    • Learning with Errors
    • Regev's Encryption
  • Homework 2 due on Wednesday

    Homework 3 out on Thursday

    7 Feb 14th, 16th
  • Lattice Based Crypto II
    • Fully Homomorphic Encryption
    • Gentry-Sahai-Waters scheme
    • Bootstrapping
  • Zero Knowledge Proofs I
    • Interactive Proofs
    • Zero-Knolwedge
    • The Goldwasser-Micali-Rachoff protocol for Graph 3-Coloring
    8 Feb 21st, Feb 23rd
  • No class on Feb 21st, Happy President's Day!
  • Zero Knowledge Proofs II
    • Proof of Knowledge for Discrete Logarithm
    • Honest Verifier Zero-Knowledge
    • Fiat-Shamir Transformation

    Homework 3 due on Wednesday

    Homework 4 out on Thursday

    9 Feb 28th, March 2nd
  • Two Party Computation
    • 2PC definition
    • Garbled Circuits
    • Oblivious Transfer
  • Multi Party Computation
    • MPC definition
    • Secret Sharing
    • the Beaver-Micali-Rogaway protocol
    10 March 7th, 9th
  • Obfuscation
    • Indistinguishability Obfuscation
    • Application: Functional Encryption
    • From Functional Encryption back to IO
    • Construction of Functional Encryption

    Homework 4 due on Wednesday

    11 March 14 to 18
  • Take home final
    • For those opt in for take-home final, it will be between 14th to 16th.
  • Take home final
    • For those opt in for project, it will be due on 18th.