In Semester 1, 2022-2023, I will be teaching CS 6846: Quantum Algorithms and Cryptography.
Course Description
The course will cover a selection of foundational topics in quantum cryptography. This course has a large overlap with CS 7260 but has a greater focus on using quantum algorithms to design cutting edge cryptography. The advent of quantum computers has created an exciting (though in some ways, unfortunate) impact on cryptography. Quantum computers, which harness the power of quantum mechanics, have demonstrated surprising power over classical computers -- in particular, a famous algorithm by Shor demonstrates that most of modern cryptography, believed to be secure against classical computers, is completely insecure against quantum computers.
In this course, we will study the foundations of quantum computing and the important role of quantum computers in cryptography. We will study the basics of quantum computing, speedups offered by quantum algorithms, attacks on cryptography using quantum computers, design of cryptosystems resilient to quantum attacks and (if time allows) cryptographic protocols using quantum physics, such as quantum key distribution, quantum money, and more.
No prior information about quantum mechanics will be assumed.
Administrative Information
Lectures are Wednesdays 2:00- 3:30 pm and Thursday, 3:30-5:00 pm in MSB 359. The first lecture is on Wednesday 27th July at 2 pm.
Pre-requisites.
There are no formal prerequisites for the course. In particular, I will not assume any background in quantum information/physics/mechanics or in cryptography. But the course will ask for strong mathematical maturity, particularly familiarity with theory of computation and algorithms. A good working knowledge of linear algebra and probability is also required.
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.
Requirements.
- Class Participation: 10%
- Scribe notes: 10%
- Project and class presentation : 50%
- Assignments : 30%
Policies and Grades.
Collaboration is encouraged but you must write up solutions on your own. You must also write the names of all the people you discussed the problem with. In case you find material that will help you in solving some problems, you should mention the source in your writeup.
I expect all students to behave according to the highest ethical standards. Any cheating or dishonesty of any nature will result in failing the class.
Resources
- This course by Dakshita Khurana, UIUC.
- This course by Mark Zhandry, Princeton.
-
These lecture notes by Thomas Vidick, Caltech.
- These lecture notes by Ronald de Wolf, CWI.
- For quantum computing, these lecture notes by Regev and these by O'Donell are great resources.
There are no required text books though the book
quantum computation and quantum information by Nielson and Chuang is useful.
Lecture Summaries
Lecture |
Topic |
Notes |
Additional references |
Lec 1 |
Overview of course. |
Slides |
Princeton, Lecture 1 in CMU notes. |
Lec 2 |
Basics of Quantum Information. |
Notes |
Lec 1, 2 in UIUC notes, Lec 2 in Princeton notes, and Lec 0 in Caltech notes. |
Lec 3 |
Quantum Computation and No Cloning. |
Notes td>
| Lec 3 in UIUC notes, Lec 2 in Princeton notes. |
Lec 4 |
Going Beyond Classical |
Notes td>
| Lec 4 in UIUC notes, Lec 3 in Princeton notes. |
Lec 5 |
Deutsch and Deutsch-Jozsa |
Notes td>
| Lec 4 and 5 in UIUC notes, Lec 4 in Princeton notes. |
Lec 6 |
Simons and Bernstein-Vazirani |
Notes td>
| Lec 5 and 6 in UIUC notes, Lec 4 in Princeton notes. |
Lec 7 |
Introduction to Cryptography |
Slides td>
| None |
Lec 8 |
Principles of Cryptographic design |
Slides td>
| Katz-Lindell |
Lec 9 |
Building Cryptography: Factoring, RSA, DLog. Build OWF, OWP, TDP |
Notes td>
| Katz-Lindell: Number Theory and Cryptographic Hardness Assumptions (Ch 9 in 3rd edition) |
Lec 10 |
CDH, DDH. Key Exchange and SKE. PKE: Ind-cpa security. ElGamal Encryption. |
Notes td>
| Katz-Lindell |
Lec 11 |
Random Oracle Model. RSA Encryption in ROM. |
Notes td>
| Katz-Lindell |
Lec 12 |
Finishing RSA Encryption. Boolean Fourier Analysis. |
Notes td>
| For RSA: Katz-Lindell. For Boolean Fourier Analysis: Lecture 6 of CMU notes. |
Lec 13 |
Grover's Algorithm. |
Notes td>
| Lecture 4 of CMU notes. |
Lec 14 |
Quantum Fourier Transform over Z_N |
Notes |
Lecture 7 of CMU notes. |
Lec 15 |
Simon's Algorithm over Z_N |
Notes |
Lecture 8 of CMU notes. |
Lec 16 |
Shor's Algorithm |
Notes |
Lecture 9 of UCB notes and UCI notes. |
Lec 17 |
Hidden Subgroup Problem |
Notes |
Lecture 10 of CMU notes. |
Lec 18 |
Introduction to Lattices |
Slides |
UCSD notes. |
Lec 19 |
Public Key Encryption from LWE |
Notes |
UCSD notes. |
Lec 20 |
Fully Homomorphic Encryption |
Notes |
Section 5.1 of this paper. |
Lec 21 |
Quantum Key Distribution |
Notes |
Ch. 17 of CWI notes. |
Lec 22 |
Quantum One time Pad and Encryption |
Notes |
Ch. 16 and 17 of UIUC notes. |
Lec 23 |
Quantum PKE and FHE |
Notes |
Ch. 18 and 20 of UIUC notes. |
Lec 24 |
Quantum FHE |
Notes |
Ch. 21 and 22 of UIUC notes. |
Lec 25-28 |
Student Presentations |
N/A |
N/A |
Student Presentations
Date |
Time |
Team |
Topic |
Oct 31 |
5 -5:15 |
Sumedh Ghude |
Classical Attacks on RSA |
Oct 31 |
5:15 -5:30 |
Siddharth Ambekar |
Multivariate cryptosystems |
Oct 31 |
5:30 -5:45 |
Akhil Vanukuri |
Worst case to average case reduction for LWE |
Oct 31 |
5:45 -6:00 |
Akshay Dharmaraj |
Hardness of LWE (connection to GapSVP and SIVP) |
Oct 31 |
6:00 -6:15 |
Sujay Srivastava |
Quantum Money |
Nov 2 |
2-2:15 |
Valliamai R, Nilesh Sharma |
Superposition attacks on classical cryptosystems |
Nov 2 |
2:15-2:30 |
Tarun Teja P |
Implementing Lattice based encryption and digital signatures |
Nov 2 |
2:30-2:45 |
Alan Joel J |
Lower Bounds on Quantum Query Complexity |
Nov 2 |
2:45-3:00 |
Uthirakalyani.G |
Hidden Subgroup Problem on non-abelian groups |
Nov 2 |
3-3:15 |
Manne Ruchitha |
Quantum Oracle Interrogation |
Nov 3 |
3:30-3:45 |
Shreeya Kuppili, Aadithya G.S. |
Quantum Merkle Puzzle |
Nov 3 |
3:45 - 4:00 |
Vishnu Vinod |
Variational Quantum Algorithms |
Nov 3 |
4:00-4:15 |
Chaganti K Siddhartha, Ishan Mankodi |
Quantum One time programs |
Nov 3 |
4:15-4:30 |
Shashank Ravi, Yash Bhagwat |
Quantum Indifferentiability |
Nov 3 |
4:30-4:45 |
Aditya Sadhu |
Implications of Quantum Technology on Trading and Financial Markets |
Topics
Below are some topics we will discuss in class.
- Mathematical Model for Quantum Mechanics, Single and multi-qubit quantum gates and circuits
- Entanglement, No Cloning, Quantum Parallelism.
- Quantum Algorithms: Deutsch-Jozsa, Simons, Bernstein-Vazirani.
- Quantum Foruier Transform, Grover's Algorithm, Shor's Algorithm.
- Post Quantum Crypto: Introduction to lattices, codes, isogenies
- Useful Lattice Problems. Learning with Errors and Short Integer Solution problem. Connection to dihedral hidden subgroup problem.
- Basic Primitives. Post quantum public key encryption, signatures.
- Quantum Hardness of Lattice Problems.
- Key distribution: Classical and Quantum
- Random Oracles: Classical and Quantum.
- Secret and Public Key Encryption: Classical and Quantum.
- Homomorphic Encryption: Classical and Quantum.
- Quantum Money.