1 Opening Remarks
1.1 What is post-quantum crypto?
Quantum computers are not like classical computers, in the sense that while classical computers work on bits, 0s and 1s, quantum computers work on qubits. Instead of being either in the state 0 or 1, these qubits can be in a superposition of the two states. Using this difference in structure, quantum computers can perform some calculations very quickly.
Designing clever algorithms that take advantage of the way qubits interact, has already delivered attacks existing and ubiquitous crypto systems. For example, Shor’s algorithm (1997) factors large integers very quickly, breaking RSA. Shor’s algorithm also computes discrete logarithms, thereby breaking Elliptic curve cryptography. Another example of a widely known quantum algorithm is Grover’s algorithm (1996). This algorithm accelerates search, reducing a brute force attack on a symmetric cipher (with a 256-bit key) from \(~2^{256}\) steps classically, to \(~2^{128}\) steps quantumly.
Because of these attacks that are made possible by quantum computers, we need to secure our crypto systems against quantum attacks. Not only developing but also deploying new standards in a thorough and secure way takes years, waiting for a quantum computer to become available is not feasible. Additionally, harvest-now-and-decrypt-later attacks mean that super sensitive data already needs to be protected against such attacks today.
Post-quantum crypto is about cryptographic systems that are classical (e.g. they run on classical computers) but withstand attacks executed using Quantum computers.
To fulfill these expectations, NIST has run a PQC standardization process. In this, researchers worldwide enter a competition where they suggest and analyze signature as well as encryption schemes. NIST picks the winners after multiple rounds of competition (e.g. Kyber, Dilithium, Falcon, Sphincs).
This lecture is about methods in post-quantum crypto. We will look at some candidates for algorithms, as well as some unique challenges that the quantum setting brings with it. To reiterate: the goal of post quantum cryptography is to deliver cryptographic protocols that run on classical computers, but withstand quantum attacks. When doing this, two branches of PQC exist in practice.
The first branch concerns itself with finding and understanding quantum attacks. Figuring out which schemes are not secure against quantum attacks, and especially why they are not secure is important. This helps peer review the existing attacks, preventing weak algorithms from being used in the real world. And, even better, the learnings from this help us understand how to better secure our own schemes from exactly these attacks. (Or maybe how secure is secure enough)
Additionally, we want to find secure schemes, and then prove that they are actually secure. There are two approaches to constructing schemes. Ideally, you would want provable security, where you can mathematically guarantee certain properties of our system. Sometimes, however, that is not possible. (This of course does not mean that the maths say its insecure, just that the maths are maybe not applicable.) Whenever mathematically proving security is not feasible, we follow best practices and make use of the peer-review mechanism to strengthen trust in our scheme.
However, even the provably secure schemes are often based on a computational hardness assumptions. These assumptions are then treated similarly to the best-effort schemes were in the first place.
In this lecture we will see schemes out of both of these branches.
If you want to read more in-depth about these topics, take a look at (2010) for the quantum background, as well as (2007) and (2021) for classical crypto notions. The concepts from classical crypto are still very useful, since many of the concepts in this lecture are analogous concepts.