1  Introduction

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 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 . 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.