s MIT 6.S895 Quantum Cryptography (Spring 2024)

MIT 6.S895 (Spring 2024)
Quantum Cryptography


Course Description

This course is an introduction to the many ways quantum computing and cryptography intersect. Topics will include uniquely quantum cryptographic primitives such as quantum key distribution and quantum money, post-quantum cryptography (classical cryptography that is secure against quantum attackers), the use of cryptography in verifying quantum devices, as well as unclonable cryptography. Some familiarity with both quantum computing and cryptography is assumed.

The audience is graduate students interested in quantum computing, cryptography, or more broadly the theory of computing. Students are expected to have some familiarity with the basic notions of quantum computing and cryptography, and to be mathematically mature (comfortable with writing proofs, and with linear algebra and basic notions in group theory and number theory).

Prerequisites: Students are expected to be familiar with the basics of quantum information and computation (at the level of 6.6410, Quantum Computation, or 6.6420, Quantum Information Science) and the basics of cryptography (at the level of 6.5620 Foundations of Cryptography) or obtain the permission of instructors.

Course Information

INSTRUCTORS Anand Natarajan
Email: anandn at mit dot edu

Vinod Vaikuntanathan
Email: vinodv at mit dot edu
LOCATION AND TIME Tuesday and Thursday 11:00-12:30pm in 45-102 (in the new Schwarzman College of Computing building).
TAs Tina Zhang
Email: tinaz at mit dot edu
Office hours: TBD. Location: TBD.
RESOURCES The main references will be the course materials including lecture notes, slides and/or videos. We will also post relevant papers after every lecture. Here are a few supplementary references for the entire course material.

Lecture notes
  1. John Preskill's Caltech lecture notes on quantum computation
  2. Ronald de Wolf's CWI lecture notes
  3. Ryan O'Donnell's CMU lecture notes on quantum information and computation
  4. Andrew Childs' Maryland lecture notes on quantum algorithms
  5. Ma and Vazirani's Berkeley course on quantum cryptography
  6. Henry Yuen's Columbia course on quantum complexity and cryptography.
  7. Khurana's UIUC course on quantum cryptography
  1. Nielsen and Chuang's classic book
  2. Watrous' book on quantum information (online version)
  3. Scott Aaronson's textbook (online version)
  4. Vidick and Wehner's book on quantum cryptography
PIAZZA We will use Piazza for class communication. Please ask your questions there, so that other students can see the questions and answers.
ASSIGNMENTS AND GRADING Grades will be determined based on 2 problem sets (20% each) and a final project, including a project presentation and a writeup (60%). The final projects can be done in groups of at most two.
COLLABORATION POLICY Collaboration is permitted and encouraged in small groups of at most three students. You are free to collaborate in discussing answers, but you must write up solutions on your own, and must specify in your submission the names of any collaborators. Do not copy any text from your collaborators; the writeup must be entirely your work. Do not write down solutions on a board and copy it verbatim into Latex; again, the writeup must be entirely your own words and your own work and should demonstrate clear understanding of the solution. Additionally, you may make use of published material, provided that you acknowledge all sources used.

Schedule (tentative and subject to change)

Lecture Topic
Lecture 1 (Tue Feb 6) Quantum bootcamp + the Wiesner money scheme [Lecture Notes]
Lecture 2 (Thu Feb 8) Attacks on Wiesner: cloning, Lutomirski's attack, Quantum Zeno Effect and the Elitzur-Vaidman bomb [Lecture Notes]

Lecture 3 (Tue Feb 13) Canceled due to "snowstorm"
Lecture 4 (Thu Feb 15) BB84 key exchange and security sketch

Tue Feb 20
Monday Schedule of Classes
Lecture 5 (Thu Feb 22) Symmetric subspace and de Finetti theorem

Lecture 6 (Tue Feb 27) BB84 Security Analysis Concluded: Information Reconciliation, Privacy Amplification, and Uncertainty

Lecture 7 (Thu Feb 29) Beyond BB84: Impossibility of Quantum Bit Commitment/ Uhlmann's theorem

Lecture 8 (Tue Mar 5)
Post-quantum Security 1: Pseudo-random Functions, Collapse-Binding [Lecture Notes]

Lecture 9 (Thu Mar 7)
Post-quantum Security 2: Collapse-Binding (Contd.) and Its Applications

Lecture 10 (Tue Mar 12) Jordan Lemma, Watrous Rewinding and Zero Knowledge against Quantum Attacks

Lecture 11 (Thu Mar 14) Rewinding and Zero-Knowledge (continued) Guest Lecturer: Alex Lombardi
Lecture 12 (Tue Mar 19)
Commitments and Oblivious Transfer from One-way Functions

References: Advanced Reading:
Lecture 13 (Thu Mar 21)
Pseudorandom Quantum States (PRS): definition and construction Guest Lecturer: Alex Poremba [Lecture Notes]

Tue Mar 26 Spring Break
Thu Mar 28 Spring Break
Lecture 14 (Tue Apr 2) Commitments from PRS, and oracle PRSs from weak assumptions Guest Lecturer: Luowen Qian [Lecture Notes]

Lecture 15 (Thu Apr 4)
Lattices, Gaussians and Shor Factoring [Lecture Notes]

Lecture 16 (Tue Apr 9) Regev's Algorithm for Factoring. Guest Lecturer: Seyoon Ragavan

Lecture 17 (Thu Apr 11)
Regev's worst-case to average-case reduction

Lecture 18 (Tue Apr 16) Yamakawa-Zhandry Proof of Quantumness.

Lecture 19 (Thu Apr 18)
Trapdoor Claw-free Functions and the BCMVV Proof of Quantumness

Lecture 20 (Tue Apr 23)
Quantum FHE and the CHSH Protocol

Lecture 21 (Thu Apr 25)
Proofs of Quantumness: Extracting and measuring a qubit

Lecture 22 (Tue Apr 30)
Testing multiqubit measurements: Pauli braiding + Gowers-Hatami

Lecture 23 (Thu May 2) Delegation and Remote State Preparation Guest Lecturer: Andru Gheorghiu

Lecture 24 (Tue May 7)
Uncloneable Cryptography Guest Lecturer: Jiahui Liu

Lecture 25 (Thu May 9)
Student Presentations
Lecture 26 (Tue May 14) Student Presentations

Resources (Quantum Information and Computation)

Resources (Cryptography)