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.


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


There are no required text books though the book quantum computation and quantum information by Nielson and Chuang is useful.

Homeworks


Please type up your solutions in latex. Email the instructor and the TAs your solutions.


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 Lec 3 in UIUC notes, Lec 2 in Princeton notes.
Lec 4 Going Beyond Classical Notes Lec 4 in UIUC notes, Lec 3 in Princeton notes.
Lec 5 Deutsch and Deutsch-Jozsa Notes Lec 4 and 5 in UIUC notes, Lec 4 in Princeton notes.
Lec 6 Simons and Bernstein-Vazirani Notes Lec 5 and 6 in UIUC notes, Lec 4 in Princeton notes.
Lec 7 Introduction to Cryptography Slides None
Lec 8 Principles of Cryptographic design Slides Katz-Lindell
Lec 9 Building Cryptography: Factoring, RSA, DLog. Build OWF, OWP, TDP Notes 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 Katz-Lindell
Lec 11 Random Oracle Model. RSA Encryption in ROM. Notes Katz-Lindell
Lec 12 Finishing RSA Encryption. Boolean Fourier Analysis. Notes For RSA: Katz-Lindell. For Boolean Fourier Analysis: Lecture 6 of CMU notes.
Lec 13 Grover's Algorithm. Notes 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.