CS/PH 120 Quantum Cryptography
Term: Fall 2016
Lectures: TT 10:3012, 243 Annenberg
Instructor: Thomas Vidick, vidick@cms.caltech.edu
Office hours: Thursday 56pm, 207 Annenberg
Teaching assistants: Andrea Coladangelo ( andrea.coladangelo@gmail.com ),
Jalex Stark ( jalex@caltech.edu ), Charles Xu ( cxu3@caltech.edu ).
Office hours: Monday 45pm, 205 Annenberg
Monday 89pm, 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, 10am12pm 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!
Jump to:
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 keydistribution
 Week 9  Perfect security from physical assumptions
 Week 10  Further topics
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 ElitzurVaidman bomb tester.
 Oct. 6th Breaking Wiesner's scheme: attacks against semipermissive banks. Security against nonpermissive banks.

Oct. 11th
Density matrices and general measurements.
Draft lecture notes.  Oct. 13th Security of the classicalverification analogue of Wiesner's scheme. CPTP maps.

Oct. 18th
Security for classical and quantum encryption. The (Quantum) onetime 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. Twouniversal hashing. The prettygood 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 Twoparty 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 24 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 25 page report on the papers, and make a short 10minute 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 nonexhaustive: 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 copyprotection, 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 MonogamyofEntanglement Game With Applications to DeviceIndependent 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.
 Positionbased 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.