MIT 6.S895 (Spring 2024)
Quantum Cryptography



Announcements

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
Textbooks
  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]

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

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

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

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

References:
Lecture 8 (Tue Mar 5)
Crypto bootcamp
Lecture 9 (Thu Mar 7)
Commitments and collapse-binding
Lecture 10 (Tue Mar 12) Watrous Rewinding
Lecture 11 (Thu Mar 14) Unruh's naïve rewinding Guest Lecturer: Alex Lombardi
Lecture 12 (Tue Mar 19)
Commitments and Oblivious Transfer from One-way Functions
Lecture 13 (Thu Mar 21)
Pseudorandom Quantum States (PRS): definition and construction Guest Lecturer: Alex Poremba
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 15 (Thu Apr 4)
Lattice bootcamp + discrete Gaussian states
Lecture 16 (Tue Apr 9) Simon's algorithm, Shor, Regev factoring
Lecture 17 (Thu Apr 11)
Regev lattice reduction, Yamakawa-Zhandry
Lecture 18 (Tue Apr 16) Post-Quantum Crypto: LWE encryption, Trapdoor functions and more.
Lecture 19 (Thu Apr 18)
Proofs of Quantumness: BCMVV.
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)