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.


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


Part 2: Post Quantum Cryptography from Lattices