CS 294-236: Cryptography in a Quantum World
(Spring 2023)
Course Information
Instructors: Fermi Ma and Umesh Vazirani
TA: James Bartusek
Time: Monday 2-5 PM (Hearst Mining Building, Room 410)
Office hours: by appointment
Course Description
Over the last few years, there has been an explosion of activity at the intersection of quantum and crypto. This includes new crypto functionalities impossible in the classical world, proving security of classical crypto against quantum attacks, revisiting the complexity-theoretic foundations of cryptography in a quantum world, and surprising connections to fundamental physics. Rather than presenting a sequence of results, this course will emphasize basic concepts and techniques. Since this is a rapidly evolving area, this course will also highlight key open questions and encourage students to formulate their own research problems. This will be the goal of the final project.
Lectures will only assume basic undergraduate-level background in quantum, crypto, and complexity theory, but will be targeted at students that have a sophisticated understanding of at least one of the above areas.
(Tentative) Schedule
| Date | Topic | Additional Links | Lecture Notes |
|---|---|---|---|
| 1/23/23 | Class Overview, Refresh of Cryptography, Motivating Post-Quantum Commitments | ||
| 1/30/23 | Defining Post-Quantum Commitments, Refresh of Quantum Basics, Quantum Rewinding | [Unruh16] | Handwritten notes |
| 2/7/23 | No class (QIP 2023 conference) | ||
| 2/13/23 | Constructing Collapsing Commitments, Post-Quantum Zero Knowledge, Jordan’s Lemma | [Watrous09] | Handwritten notes |
| 2/20/23 | No class (Berkeley academic holiday) | ||
| 2/27/23 | Post-Quantum Succinct Arguments and Quantum Rewinding | [CMSZ21] | Handwritten notes |
| 3/6/23 | Classically Testing a Quantum Device | Scribe notes | |
| 3/13/23 | No class (Berkeley CS visit day) | ||
| 3/20/23 | Hardness of Lattice Problems, Multiplying Quantum States, and Quantum Advantage Relative to a Random Oracle | [YZ22], Vinod’s lecture notes, Peikert’s survey | Handwritten notes |
| 3/27/23 | No class (spring break) | ||
| 4/3/23 | Uncloneable Cryptography (guest lecture by Mark Zhandry) | Scribe notes | |
| 4/10/23 | Quantum Bit Commitments and Minimal Assumptions | Handwritten notes | |
| 4/17/23 | Quantum State Commitments and Pseudorandom States | Handwritten notes | |
| 4/24/23 | Connections Between Cryptography and Fundamental Physics |
Problem Sets
Problem Set 1 (Due Feb 27)
Problem Set 2 (Due April 24)
Final Project
Due Date: May 15
Assignment: Write a report surveying research in an area of quantum (or post-quantum) cryptography that was not directly covered in lecture, covering roughly 2-4 papers. A successful report should provide a clear, concise, and mostly self-contained introduction to the area, while also highlighting and motivating the key open questions in the area. Making progress on open questions would be fantastic, but not required.
Additional Resources
Quantum:
Cryptography:
Quantum Cryptography: