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    
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)    
4/10/23 Pseudorandom States, Quantum Commitments, and Connections to Complexity Theory    
4/17/23 Quantum Cryptography and Fundamental Physics    
4/24/23 Student Presentations    

Problem Sets

Problem Set 1 (Due Feb 27)

Additional Resources



Quantum Cryptography: