CS/PH 120 Quantum Cryptography

Term: Fall 2016
Lectures: TT 10:30-12, 243 Annenberg

Instructor: Thomas Vidick, vidick@cms.caltech.edu
Office hours: Thursday 5-6pm, 207 Annenberg

Teaching assistants: Andrea Coladangelo ( andrea.coladangelo@gmail.com ),
Jalex Stark ( jalex@caltech.edu ), Charles Xu ( cxu3@caltech.edu ).
Office hours: Monday 4-5pm, 205 Annenberg
Monday 8-9pm, 106 Annenberg

Announcements

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 description

This 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 outline

The 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

The last two weeks will be released beyond the regular Caltech quarter, but we will cover some of the material, including the topic of delegated computation, in class.

Prerequisites

I 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 workload

Students 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).

Lectures

Sept. 27th. Introduction to cryptography. Why use quantum information for cryptography? Basics of quantum information: qubits, basis measurements, unitary operations.
Lecture notes.
Sept. 29st. 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.
Oct. 11th Density matrices and general measurements.
Draft lecture notes.
Oct. 13th Security of the classical-verification analogue of Wiesner's scheme. CPTP maps.
Oct. 18th Security for classical and quantum encryption. The (Quantum) one-time pad.
Lecture notes.
Oct. 20th Notions of security: perfect security vs breaking correlations.
Oct. 25th Secret sharing.
Oct. 27th Nonlocal games.
Nov. 1st Measuring randomness: notions of entropy.
Lecture notes.
Nov. 3rd Guessing games.
Nov. 8th Privacy amplification.
Lecture notes.
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.

Homework

Due Oct. 11th: HW1, Solutions.
Due Oct. 18th: HW2. Solutions.
Due Oct. 25th: HW3. Solutions.
Due Nov. 2nd: HW4. Solutions.
Due Nov. 8th: HW5. Solutions.
Due Nov. 15th: HW6. Solutions.
Due Nov. 22nd: HW7. Solutions.
Due Nov. 29th: HW8. Solutions.

Projects

As 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.

Resources

Your 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.