Introduction to quantum cryptography

Introductory course on quantum cryptography. Subjects: perfect secrecy and the one-time pad ; quantum money ; quantifying information and uncertainty ; entanglement ; quantum key distribution ; two-party cryptography ; the bounded storage model ; additional topics depending on time and interest. 

Teacher: thomas.vidick#epfl.ch

Assistant: zihan.hu#epfl.ch

Schedule:

- Lectures on Tuesdays, 10h15-12h and Thursdays, 1:15-2

- Exercises session, 2:15-3h 

- Thomas' office hours on Thursdays, 3-4pm, BC110. Everyone is welcome to discuss class topics

Reference book: Introduction to quantum cryptography, Cambridge university Press, 2023

Homework: 4 problem sets and 2 reading exercises in total. Given bi-weekly, out on Friday evening, due Tuesday+11 in the evening (exact dates TBD)

Exam and grading: homework 20% (4 problem sets * 20% each + 2 reading exercises * 10% each)  + midterm 35% + final 45%

Final exam date: January 13th from 9h15 to 12h15

We covered the definition of perfect security for symmetric-key encryption. We defined and showed security of the classical and quantum one-time pads. We proved Shannon's theorem on the length of keys. 

In terms of the lecture notes, we covered essentially Section 1.5 in the pdf file. If you are using the book, this is Section 2.5. We also reviewed some of the preliminary material on density matrices, CQ states, the partial trace, and the Pauli matrices. 

This week, on Tuesday we introduced the definitions for (private) key quantum money. We saw a construction, Wiesner's scheme, and tried a couple attacks on it. This corresponds to sections 2.1, 2.2, and 2.3.1 in the notes. 

On Thursday we gave a brief introduction to semidefinite programming. The notes contain a little more detail than what we saw in class. (In particular, Section 2 was not covered and will be covered on Tuesday.)

This week we conclude our discussion of quantum money. On Tuesday we show a bound on the security of Wiesner's quantum money scheme, using a semidefinite program and semidefinite programming duality. This part is discussed in the notes posted this week. 

On Thursday we discussed attacks on Wiesner's scheme in a relaxed model where the adversary is allowed to make queries to a verification oracle. This corresponds to Section 2.4 in the "Chapter 2 notes" posted last week. 

This week we discussed entanglement, the CHSH game, and monogamy. This corresponds to essentially all of Chapter 3, except for the discussion on superdense coding. 

This week we discussed the problem of quantifying information, or uncertainty, in the presence of side information. We covered essentially the entirety of Chapter 4 in the book (see the notes pdf), except for the paragraphs on the smooth min-entropy and on the general (quantum-quantum) quantum conditional min-entropy. We ended the week with a very brief introduction to privacy amplification; this will be the topic of next week's notes. 

We covered the topic of privacy amplification, and showed how to solve it using strong extractors. We gave a construction of extractors based on 2-universal families of hash functions and showed its security. This corresponds to Chapter 5 in the book.

We gave the correctness and security definition for quantum key distribution, and discussed the post-processing step of information reconciliation. This is the contents of Chapter 6. 

We covered BB'84 quantum key distribution, and the arguments for correctness and security. This is essentially the entirety of Chapter 7, except Sections 7.3.1 and 7.3.3 which we did not cover in class. 

We reviewed the proof of correctness and security of the BB'84 protocol for QKD. Then, we discussed the notion of device-independent security and sketched how to achieve it based on the CHSH game. Finally, we discussed "rigidity" of the CHSH game, namely the uniqueness of optimal strategies in it. 

In terms of the notes, this corresponds to Section 8.1 of Chapter 8, Section 8.2 only for intuition, and Section 8.3 partially but the technical calculations are beyond the scope of the class. 

This week we started discussing two-party cryptography. We covered coin-flipping (Section 9.1), the general framework for two-party cryptography (Section 9.2) and oblivious transfer (Section 9.3).

This week we continued our discussion of two-party cryptography. On Tuesday we introduced bit commitment, studied and broke a simple protocol, and showed a general impossibility result (Section 9.4). On Thursday we built oblivious transfer from bit commitment and briefly introduced the bounded storage model (Chapter 10 except Sections 10.3.2 and 10.3.3). 

This week we revisit the notion of encryption of quantum messages, including approximate encryption. This corresponds to Section 11.1 in the notes, except for Section 11.1.2 which we did not discuss. In class, we did a bit more on computational security than is in the notes; up to the level required to solve the exercise sheet (essentially, definition of a PRF). 

We discussed the definition of delegated computation and a protocol based on the idea of magic states. This is sections 12.1 and 12.2 (except section 12.2.3) in the notes.