COS 597A - Quantum Cryptography (Fall 2018)

Course Information

Instructor: Mark Zhandry
Time: MW 1:30pm - 2:50pm
Location: TBA
Office Hours: By appointment
Grading: Based on homeworks every 2-3 weeks, scribing some lectures, final project

Course Description

Quantum computers, harnessing the power of quantum physics, are poised to deliver significant and far-reaching impacts to cryptography. Substantial progress is being made in developing these devices, indicating that quantum computing may be viable in the next couple decades. This course will discuss the important role quantum computing will play in cryptography, covering topics such as:
  1. Quantum attacks on cryptography
  2. Cryptosystems resilient to quantum attacks
  3. Protocols using quantum physics, such as quantum key distribution, quantum money, and more
Prerequisites: Basic familiarity with computability and complexity theory, such as that covered in COS 340 (Turing Machines, P vs NP, NP-completeness, etc). Familiarity with basic notions in cryptography (encryption, authentication, security definitions) will be a plus, but not required. No prior knowledge of quantum mechanics or physics is assumed.

Tentative Schedule (subject to change)

Lecture Topic Readings Scribe Notes
1 - W, 9/12 Course introduction [1]
2 - M, 9/17 A Mathematical Model for Quantum Mechanics [2]
3 - W, 9/19 Quantum Gates and Quantum Computing [3]
4 - M, 9/24 Quantum Algorithms [4]
5 - W, 9/26 Quantum Fourier Transform, Grover's Algorithm [5]
6 - M, 10/1 Shor's Algorithm [6]
7 - W, 10/3 Shor's Algorithm [7]
8 - M, 10/8 Lattice Cryptography [8]
9 - W, 10/10 Lattice Cryptography [9]
10 - M, 10/15 Dihedral Hidden Subgroup Problem [10]
11 - W, 10/17 Other Post-quantum Cryptosystems
12 - M, 10/22 Quantum Random Oracle Model [1], [2], [3] [12]
13 - W, 10/24 Quantum Rewinding [4], [5] [13]
M, 10/29 No Class - Fall recess
W, 10/31
14 - M, 11/5 More attacks on Post-Quantum Crypto [6], [7] [14]
15 - W, 11/7 No Cloning, Quantum Money [15]
16 - M, 11/12 No Cloning, Quantum Money
17 - W, 11/14 No Cloning, Quantum Money [17]
18 - M, 11/19 Certifiable Randomness [18]
W, 11/21 No Class - Thanksgiving
19 - M, 11/26 Encrypting Quantum States
20 - W, 11/28 Authenticating Quantum States [20]
21 - M, 12/3 Key Recycling [21]
22 - W, 12/5 Quantum Key Distribution [22]
23 - M, 12/10 Student Presentations
24 - W, 12/12 Student Presentations

Homework Assignments

Homework 0: Please sign up for scribing lectures here. For now, sign up for two lectures.

Homework 1: [HW1] Due October 10

Homework 2: [HW2] Due October 24

Homework 3: [HW3] Due December 5


Instructions for Homeworks: Please type up your solutions (LaTeX preferred). Either email your solutions to (preferred) or print them out and hand them in during class by the due date.

Templates for Scribing

template.tex
LN1.tex

Final Project

[PR]

Due Dates: