Welcome to the Spring 2022 web page for Quantum Cryptography

Course Overview

This course will cover a selection of cutting-edge topics in quantum cryptography. We will begin with a brief introduction to quantum computing, and then discuss the influence of quantum computing on cryptography. We will cover:
1. Quantum attacks on classical cryptography and how to achieve resilience to them
2. Protocols that use quantum resources, such as quantum key distribution, copy-protection and quantum money
3. Interactive proofs with quantum devices
No prior background in quantum information/quantum physics/mechanics or in cryptography will be assumed, although students are expected to be well-versed with basic concepts in the theory of computation (P vs NP, Turing Machines, reductions), and are expected to pick up concepts in quantum cryptography along the way.

We will understand how an adversary that breaks advanced protocols can be transformed into an adversary that contradicts basic mathematical assumptions. Our focus will be on understanding key ideas in cryptography research published over the last few years, and identifying new directions and problems for the future.

Course Credits: 4
Time: Tuesdays and Thursdays, 2.00 - 3.15 pm
Location: 1302 Siebel. First week online on zoom.
Instructor: Dakshita Khurana, dakshita@illinois.edu
Office Hours: Tuesdays 4- 5 pm (same zoom link as above).
TA: Amit Agarwal, amita2@illinois.edu

Zoom Link: Click here.

Note: Students are encouraged to drop by during office hours (or set up, by email, an appointment to meet) within the first 3 weeks. This will help me learn more about your interests and what you hope to learn from this class, and I can help you with a choice of topic for your project.

We will have lecture notes uploaded to this webpage and videos uploaded to this mediaspace channel, which will serve as the main resource for this course. Due to privacy regulations and the interactive nature of this course, videos can unfortunately only be viewed registered class participants.

Here is a list of additional resources.

Lectures and Books on Quantum Computing

Books and Lecture Notes on Cryptography in General

Similar Course Offerings

Grading (subject to change until Jan 22)

10%: Class Participation.
The class is intended to be as interactive as possible: you are strongly encouraged to ask questions and offer answers. I will often end my lectures with open-ended questions that we will answer interactively during the next class. These questions will be easy to answer if you attend every lecture. Reading prescribed material before the next lecture is recommended to better understand the contents of the course.

10%: Scribe Notes. You can find a running collection of scribe notes here.
Scribe notes are a complete, polished write-up of a lecture, with references and technical details carefully filled in. These will serve as the primary technical material for this course. Every student should expect to scribe once, either solo or in teams of 2 depending on class size. At the beginning of every lecture, I will ask for volunteers to write the scribe notes for the day. Please do not volunteer if there is a chance that you will drop the course before you submit your scribe notes. Preparing these notes will help you internalize the material at a new level, by thinking through the significance of the material and converting every proof outline discussed in class to a rigorous proof. Please typeset your scribe notes in LaTeX using the template here. Please make a new editable copy of the file on overleaf and make changes there. You have one week to prepare the scribe notes. More precisely, the scribe notes for a Tuesday lecture are due at 5 pm the following Tuesday, and the scribe notes for a Thursday lecture are due at 5 pm the following Thursday. To submit, please make a private piazza post (visible to instructors and TAs) and link to your overleaf copy.

30%: Assignments.
You will have 3 written assignments over the course of the semester. These will be due in the first half of the course to leave you with sufficient time to devote to your project and videos.

50%: Project or Video Snippets.
Individually or in groups of 2, you will either:
- Record clear video snippets that perform a deep dive into an area in quantum cryptography with a general audience in mind, bonus points for clever ways to make it interesting and accessible! 
- Attempt original research to answer some open problem in quantum cryptography, on a topic of your choice.
 I am happy to consult individually with you during office hours or by appointment to provide guidance. You should feel free to work individually, or in teams of 2, and grades will be calibrated accordingly. 

How to be Successful in this Course.
Attendance and class participation are important for success in this course. Please do your best to attend every lecture. Active participation in class will take you a long way. If you don't understand something, ask. If you didn't understand, there is a good chance that many others didn't, and you are likely doing everyone a favor. Read in advance of the next class, and be prepared to answer my questions during class.

If you are not comfortable with P versus NP, circuits, (non-uniform) Turing Machines, please read Sections 1, 2.1 and 6.1 from this textbook before the course begins. We will rely heavily on linear algebra throughout this course. Brush up your understanding of linear algebra here.

Course Schedule

The following is a tentative schedule and is subject to change.

Before the Course.
This course will assume familiarity with basic concepts in complexity theory. If you have not had prior exposure, please read Sections 1, 2.1 and 6.1 (all required), and section 10 (optional) from this textbook. 

Date Topic Notes and Scribbles Additional Resources
      Boaz Barak's math background notesA Note on Negligible Functions
01/18

Reversible Computation, Complex Numbers

Scribe notes
Scribbles Lec 1

O'Donnell's Notes: Lectures 1-2
Zhandry's Notes Lec 1
01/20

Quantum Mechanics:
Model, Unitaries, Measurements

Scribe notes
Scribbles Lec 2

O'Donnell's Notes: Lectures 2-3
Zhandry's Notes Lec 2

02/25

Quantum Gates and Circuits, Entanglement, No-Cloning

Scribe notes
Scribbles Lec 3

O'Donnell's Notes: Lectures 2-3
Zhandry's Notes Lec 3

02/27

Quantum Algorithms

Scribe notes
Scribbles Lec 4
O'Donnell's Notes: Lectures 4-5
Zhandry's Notes Lec 4
02/01

Simon's Algorithm, Fourier Basis

Scribe notes
Scribbles Lec 5
O'Donnell's Notes: Lecture 6
02/03 Period-Finding Scribe notes
Scribbles Lec 6
O'Donnell's Notes: Lectures 7-8
02/08

Shor's Algorithm

Scribe notes
Scribbles Lec 7

O'Donnell's Notes: Lectures 8-9

02/10

Quantum Fourier Transform wrap-up

Scribe notes
Scribbles Lec 8

O'Donnell's Notes: Lectures 8-9

02/15 Mixed States Scribe notes
Scribbles Lec 9
 
02/17

-- no class --

   
02/22

Quantum Key Distribution - I

Scribe notes
Scribbles Lec 10
Sampling in a quantum population
02/24 Quantum Key Distribution - II Scribe notes
Scribbles Lec 11
Sampling in a quantum population
03/01

Quantum Oblivious Transfer - I

Scribe notes
Scribbles Lec 12
Sampling in a quantum population
03/03

Quantum Oblivious Transfer - II

Scribe notes
Scribbles Lec 13
Sampling in a quantum population
03/08

Quantum Oblivious Transfer - III

Scribe notes
Scribbles Lec 14
Sampling in a quantum population, Section 7.6 in these notes
03/10

Quantum Random Oracles, Introduction to Encryption

Scribe notes
Scribbles Lec 15
Lectures 5, 9, 10 in this course  
03/15

No class/spring break

  Spring break
03/17

No class/spring break

  Spring break
03/22 Encrypting Quantum States - I Scribe notes
Scribbles Lec 16
These lecture notes from a previous offering: Lecture 3Lecture 4Lecture 5Lecture 9Lecture 10
03/24

Encrypting Quantum States - II

Scribe notes
Scribbles Lec 17
Same notes as above, this video
03/29

Public Key Encryption

Scribe notes
Scribbles Lec 18
These lecture notes from a previous offering: Lecture 9Lecture 10
03/31

Fully Homomorphic Encryption for Classical Circuits

Scribe notes
Scribbles Lec 19

Scribe notes from a previous offering: Lecture 11

GSW Homomorphic Encryption from Learning with Errors , Lecture Notes with some Simplifications

04/05

Quantum Fully Homomorphic Encryption - I

Scribe notes
Scribbles Lec 20
Homomorphic Encryption for Quantum Circuits
04/07 Quantum Fully Homomorphic Encryption - II Scribe notes
Scribbles Lec 21
Homomorphic Encryption for Quantum Circuits
04/12

-- no class --

   
04/14

-- no class --

   
04/19 Homomorphic encryption wrap-up Scribe notes
Scribbles Lec 22
 Homomorphic Encryption for Quantum Circuits
04/21

Classically Testing a Qubit - I

Scribe notes
Scribbles Lec 23
Lecture notes by Thomas Vidick
04/26 Classically Testing a Qubit - II Scribe notes
Scribbles Lec 24
 Lecture notes by Thomas Vidick
04/28 A Simple test for QMA, Classical Verification of
Quantum Computation, Introduction to Quantum Money
Scribe notes
Scribbles Lec 25
 Lecture notes by Thomas Vidick
05/03

Quantum Money

Scribe notes
Scribbles Lec 26
 

Web Analytics

The intent of this section is to raise student and instructor awareness of the ongoing threat of bias and racism and of the need to take personal responsibility in creating an inclusive learning environment.

The Grainger College of Engineering is committed to the creation of an anti-racist, inclusive community that welcomes diversity along a number of dimensions, including, but not limited to, race, ethnicity and national origins, gender and gender identity, sexuality, disability status, class, age, or religious beliefs. The College recognizes that we are learning together in the midst of the Black Lives Matter movement, that Black, Hispanic, and Indigenous voices and contributions have largely either been excluded from, or not recognized in, science and engineering, and that both overt racism and micro-aggressions threaten the well-being of our students and our university community.

The effectiveness of this course is dependent upon each of us to create a safe and encouraging learning environment that allows for the open exchange of ideas while also ensuring equitable opportunities and respect for all of us. Everyone is expected to help establish and maintain an environment where students, staff, and faculty can contribute without fear of personal ridicule, or intolerant or offensive language. If you witness or experience racism, discrimination, micro-aggressions, or other offensive behavior, you are encouraged to bring this to the attention of the course director if you feel comfortable. You can also report these behaviors to the Bias Assessment and Response Team (BART) (https://bart.illinois.edu/). Based on your report, BART members will follow up and reach out to students to make sure they have the support they need to be healthy and safe. If the reported behavior also violates university policy, staff in the Office for Student Conflict Resolution may respond as well and will take appropriate action.

All members of the Illinois Computer Science department - faculty, staff, and students - are expected to adhere to the CS Values and Code of Conduct. The CS CARES Committee is available to serve as a resource to help people who are concerned about or experience a potential violation of the Code. If you experience such issues, please contact the CS CARES Committee. The Instructors of this course are also available for issues related to this class.

Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional well-being. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University's resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.

Counseling Center: 217-333-3704, 610 East John Street Champaign, IL 61820

McKinley Health Center:217-333-2700, 1109 South Lincoln Avenue, Urbana, Illinois 61801

University wellness center: https://wellness.illinois.edu/