Quantum Algorithms and Cryptography

ABOUT THE COURSE: 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, 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, classical cryptography and how it is broken by quantum computers, design of cryptosystems resilient to quantum attacks and cryptographic protocols using quantum physics, such as quantum key distribution, quantum public key encryption and quantum fully homomorphic encryption.PREREQUISITES:Theory of Computation, Design and Analysis of Algorithms, Foundations of Cryptography

Week 1: Basics of Quantum InformationWeek 2: Entanglement, No Cloning, Quantum Parallelism.Week 3: Quantum Algorithms: Deutsch-Jozsa, Simons, Bernstein-Vazirani,Week 4: Introduction to Cryptography, principles of cryptographic design, building cryptography from RSA, Discrete LogWeek 5: Key exchange, Symmetric and public key encryption, Random Oracle Model, RSA and Elgamal encryptionWeek 6: Boolean Fourier Analysis, Grover's Algorithm, Quantum Foruier TransformWeek 7: Shor's Algorithm, Hidden subgroup problemWeek 8: Post Quantum Crypto: Introduction to lattices, Useful Lattice Problems. Learning with Errors and Short Integer Solution problem. Connection to dihedral hidden subgroup problem.Week 9: Public key encryption and fully homomorphic encryptionWeek 10: Quantum key distribution, Quantum one time padWeek 11: Quantum public key encryptionWeek 12: Quantum fully homomorphic encryption