Post-Quantum Secure Cryptography

Overview:

• Introduction to Quantum Computing
• Shor’s Algorithm: a quantum algorithm that breaks classically hard problems like the factorization of integers.
• Algebraic Lattices: an introduction to algebraic lattices and hard problems on lattices like the shortest vector problem; the foundation to build secure post-quantum secure cryptosystems
• Learning with Errors (LWE) and Ring Learning with Errors (R-LWE): these problems are shown to be at least as hard as certain algebraic lattice problems and form an intermediate step towards efficient post-quantum secure cryptosystems.
• Post-Quantum Secure Cryptosystems: Regev’s cryptosystem built on LWE and the Brakerski-Gentry-Vaikuntanathan scheme built on R-LWE. The latter scheme is even a (leveled) fully homomorphic encryption scheme, which means that one can use this scheme to carry out computations on encrypted data. 
•  Applications of Lattice-Based Cryptosystems: Efficient Secure Multi-Party Computation protocols, that is, protocols to compute arbitrary functions with input from different parties where the parties do not have to reveal their inputs to the other parties. Such protocols can, for example, be used to do privacy-preserving machine learning, i.e., classify data and train models without parties having to reveal their data or models. 

Cryptography is everywhere! We heavily rely on cryptography in our everyday life, for example, when we do online shopping and online banking, pay with credit or debit card, open doors with electronic keys, or when we use social networks, instant messengers, online games, WiFi, mobile networks, or electronic currencies.

In all of these applications the most widely used cryptosystems, like RSA encryption and elliptic curve cryptography, are built on the hardness of certain algebraic problems, like the factorization of integers. While these problems withstood all attacks by classical computers so far, it is also known that a suitable quantum computer could easily solve the underlying mathematical problems in polynomial time and therewith break the corresponding cryptosystems. For example, the famous quantum algorithm by Shor can break the factorization problem efficiently. 

Recent progress in the development of quantum computers led researchers and governmental organizations, e.g. the National Institute of Standards and Technology (NIST), to start the search for new cryptosystems usable on classical computers that can withstand attacks by quantum computers - so-called post-quantum cryptosystems. Although there are currently no sufficiently powerful quantum computers, it is still highly necessary to find and establish these post-quantum cryptographic standards in due time. This is particularly important for information which has to be kept secret for 5 or 10 years or even longer and which should not become public the moment someone constructs a powerful quantum computer.

This lecture will therefore concentrate on the state-of-the-art cryptosystems that are post-quantum secure. Post-Quantum secure cryptosystems are not only important to protect against quantum computers. They are also used to construct so-called fully-homomorphic encryption schemes, which allow you to carry out computations on encrypted data. Moreover, they are used in secure Multi-Party Computation protocols. With these protocols you can compute arbitrary functions with input from different parties where the parties do not have to reveal their inputs to the other parties. Such protocols can, for example, be used to do privacy-preserving machine learning, i.e., classify data and train models without parties having to reveal their data or models. 

The course gives a self-contained treatment of the topic of post-quantum cryptography such that no prior knowledge of the underlying mathematical or physical theory, apart from elementary algebra, is required. The necessary knowledge can for example be attained in our lecture Mathematical Foundations of (Post-Quantum) Cryptography.

You have to obtain at least 50% of all points in the homework in order to be admitted to the final exam.

The exam will either be a written exam (90 minutes) or an oral exam (30 minutes), depending on the number of participants.

Both the lecture and the exercise are held in English.