CS/PH 120 Quantum Cryptography
Term: Fall 2016
Lectures: TT 10:30-12, 243 Annenberg
Instructor: Thomas Vidick, email@example.com
Office hours: Thursday 5-6pm, 207 Annenberg
Teaching assistants: Andrea Coladangelo ( firstname.lastname@example.org ),
Jalex Stark ( email@example.com ), Charles Xu ( firstname.lastname@example.org ).
Office hours: Monday 4-5pm, 205 Annenberg
Monday 8-9pm, 106 Annenberg
- Project reports are due Tuesday 12/6 before midnight, either by email to me or in the box outside 241 ANB. Project presentations will be Thursday 12/8, 10am-12pm in 243 ANB.
- Solutions for all homeworks are up. I have a lot of graded homeworks in my office. You should pick them up: you will not improve if you don't register why you lost points!
Course descriptionThis course is an introduction to quantum cryptography. It is offered simultaneously as an EdX course. Video modules, lecture notes and quizzes will be available weekly on EdX. In class we will review the material and dive deeper.
Course outlineThe course on EdX starts October 10th, which is the third week of class. The first two weeks will be spent reviewing the basics of linear algebra, quantum information, computer science and cryptography that will be used throughout.
Starting in the third week we will follow the same outline as the course on EdX, which is the following:
- Week 0 - A crash course in quantum information
- Week 1 - From essential tools to the first quantum protocol
- Week 2 - The power of entanglement
- Week 3 - Quantifying information
- Week 4 - From imperfect information to (near) perfect security
- Week 5 - Distributing keys
- Week 6 - Quantum key distribution protocols
- Week 7 - Quantum cryptography using untrusted devices
- Week 8 - Quantum cryptography beyond key-distribution
- Week 9 - Perfect security from physical assumptions
- Week 10 - Further topics
PrerequisitesI will not assume any background in quantum information or cryptography: all the necessary background will be reviewed in the first two weeks. I will assume a solid knowledge of linear algebra and probability; the most important prereq is Math 1b. Helpful related classes to have taken are Ph 2b, 12b and CS 21, 38.
Evaluation and workloadStudents are required to:
- Familiarize themselves with the material posted on EdX ahead of class: this includes watching the videos, reading the lecture notes, and answer the quizzes (10% of the final grade).
- Attend class and participate (5% of the final grade).
- Turn in weekly problem sets (50% of the final grade).
- Complete a final project (35% of the final grade).
Introduction to cryptography. Why use quantum information for cryptography? Basics of quantum information: qubits, basis measurements, unitary operations.
Multiple qubits: the tensor product. No Cloning. Wiesner's scheme for quantum money.
Notes: For a brief introduction, see Section 18 in Unruh's notes. For much more, see also Chapter 7 in Aaronson's notes. Wiesner's 1983 paper itself is an excellent read.
- Oct. 4th. Breaking Wiesner's scheme: attacks against permissive banks. The Elitzur-Vaidman bomb tester.
- Oct. 6th Breaking Wiesner's scheme: attacks against semi-permissive banks. Security against non-permissive banks.
Density matrices and general measurements.
Draft lecture notes.
- Oct. 13th Security of the classical-verification analogue of Wiesner's scheme. CPTP maps.
Security for classical and quantum encryption. The (Quantum) one-time pad.
- Oct. 20th Notions of security: perfect security vs breaking correlations.
- Oct. 25th Secret sharing.
- Oct. 27th Nonlocal games.
Measuring randomness: notions of entropy.
- Nov. 3rd Guessing games.
- Nov. 10th Extractors against quantum side information. Two-universal hashing. The pretty-good measurement
- Nov. 15th Information reconciliation.
- Nov. 17th The BB'84 protocol for quanutm key distribution.
- Nov. 22nd Security of BB'84 via the purified protocol.
- Nov. 24th No class due to Thanksgiving.
- Nov. 29th Two-party cryptography.
- Dec. 1st Delegating quantum computations.
ProjectsAs part of the class you will work on a project. Projects can be done individually, but small groups of 2-4 are encouraged. You will pick a topic to read upon for the project. The default format will be to choose a couple papers, write a 2-5 page report on the papers, and make a short 10-minute presentation in class. The goal is to read papers that are interesting, and be critical about them. They can be old papers (such as the first paper on quantum information, introducing Wiesner's scheme for quantum money), or very recent (such as papers on quantum authentication or certified randomness generation). Here is a list of suggested topics. The list is non-exhaustive: you may choose papers not in the list as well. For each topic listed, I give one or two papers as a starting point. It is up to you to google around a little bit and find if there are more relevant (or more interesting) papers available on the same topic.
- Quantum copy-protection, by Aaronson
- Quantum money with public verification: Quantum money from hidden subspaces, by Aaronson and Cristiano, and Quantum money from knots, by Farhi et al.
- How to share a secret, by Shamir, and How to share a quantum secret, by Cleve et al.
- A Monogamy-of-Entanglement Game With Applications to Device-Independent Quantum Cryptography, by Tomamichel et al.
- The classics: Quantum cryptography: Public key distribution and coin tossing, by Bennett and Brassard, and Quantum cryptography based on Bell's theorem, by Ekert.
- Authentication: Quantum Digital Signatures, by Gottesman and Chuang, and Authentication of quantum messages, by Barnum et al.
- Randomness expansion: Chapter 5 in Colbeck's Ph.D. thesis. See also Certifiable quantum dice, by Vazirani et al.
- Position-based quantum cryptography: Quantum tagging for tags containing secret classical data. See also the Nature news & views by Brassard for an overview of subsequent developments.
- Relativistic cryptography: Secure Bit Commitment From Relativistic Constraints, by Kaniewski et al.
- Noncontextuality and its relation to nonlocality: a paper on Hardy's paradox, by Abramsky et al.
ResourcesYour main resource will be the teaching material posted on EdX. This includes video modules, lecture notes, quizzes, and pointers to additional resources available online. The material for Week 0 is already available and contains lots of background reading.
There is no textbook on quantum cryptography. A good reference on quantum information is the book Quantum Computation and Quantum Information by Nielsen and Chuang.