In Semester 2, 2020-2021, I will be teaching CS7260: Post-Quantum Cryptography.
Course Description
The course will cover the exciting impact on cryptography created by the advent of quantum computers. 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. Moreover, significant progress has been made in recent times to develop quantum computers (for instance, Google recently announced that it can demonstrate "quantum supremacy"), so it is an urgent need to base cryptography on problems that remain hard against quantum attackers.
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. In short, we'll study the fun science behind this fun poem:
If computers that you build are quantum,
Then spies everywhere will all want 'em.
Our codes will all fail,
And they'll read our email,
Till we get crypto that's quantum, and daunt 'em!
-- By Jennifer and Peter Shor
No prior information about quantum mechanics will be assumed.
Administrative Information
Lectures are Wednesdays 3:30- 4:45 pm and Fridays, 2:00-3:30 pm. Lectures are held in virtual mode, and the link is
here.
Pre-requisites.
The course CS 6111 (Foundations of Cryptography) is a pre-requisite for this course. More importantly, this course requires mathematical maturity, in particular comfortable working knowledge of linear algebra and probability.
Requirements.
- Project and class presentation : 25%
- Assignments : 30%. Assignments will be open ended in nature and collaboration is encouraged.
- Midterm :20%
- Final :25%
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. Class participation will also be taken into account when assigning grades.
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.
The first half of the course will roughly follow the outline of the first half
this course by Mark Zhandry.
These lecture notes by Thomas Viddick and
these by Ronald de Wolf are also a useful resource. There are no required text books though the book
quantum computation and quantum information by Nielson and Chuang is useful. For quantum computing,
these lecture notes by Regev and
these by O'Donell are great resources. The second half of the course will roughly follow the outline of
this course by Vinod Vaikuntanathan.
Topics
Below are some topics we will discuss in class. We'll cover some subset of these, depending on time.
Part 1: Quantum Computing breaks Number Theoretic Cryptography
- Setting it up: Mathematical Model for Quantum Mechanics, Single and multi-qubit quantum gates, No cloning theorem. Quantum circuits emulate classical circuits. Quantum Parallelism. Lecture notes for introductory material are here. We also used material from the book quantum computation and quantum information by Nielson and Chuang.
- Quantum Algorithms: Deutsch-Jozsa, Simons, Bernstein-Vazirani, Grover's, Shor's. We used material from Nielson-Chuang and Zhandry's notes.
Part 2: Post Quantum Cryptography from Lattices
- Introduction to lattices. Excellent notes here. We used slides by Micciancio (here) and Peikert (here).
- Useful Lattice Problems. Learning with Errors and Short Integer Solution problem. Connection to dihedral hidden subgroup problem. Some good notes are here and here.
- Basic Primitives. Post quantum public key encryption, signatures. Good notes are here.
- Lattice Trapdoors and how to build them. We will use material from a Simon's Workshop.
- IBE, IPE, ABE: Advanced cryptographic primitives such as identity based encryption, inner product encryption, attribute based encryption. We will use material from the Simon's Workshops and Vinod's notes.
- Fully Homomorphic Encryption: A nice survey is here.
FHE of BV11 and Brakerski 12: References are here and here. The modulus reduction trick from BGV12 is described in these notes. FHE of GSW13 and (possibly) the improvement of BV14. Some useful notes are here.
Part 3: Why are lattice problems quantum hard?
Here is an interesting talk by Zvika Brakerski on lattices and quantum hardness. Here is the original paper by Regev that establishes the connection between LWE and dihedral HSP. We will use these lecture notes as a baseline for our discussion.
Project
Some project ideas are here. You are welcome to choose any topic outside this list as well.