Kyber and Post-Quantum Crypto - How does it work?

Post-Quantum Crypto is the art of inventing asymmetric cryptography that can withstand large quantum computers. This relatively young subject becomes more and more relevant as Shor’s algorithm would break all of today’s asymmetric cryptography once a large enough quantum computer can be build. Therefore RSA, Elliptic Curve Crypto, Diffie-Hellman, DSA and friends could soon be obsolete.

Kyber (formerly known as New Hope) is among the first post-quantum schemes to be standardized and already found its way into products. As a lattice-based system, Kyber is fast and its security guarantees are linked to an NP-hard problem. Also, it has all the nice mathematical ingredients to confuse the hell out of you: vectors of odd-looking polynomials, algebraic rings, error terms and a security reduction to “module lattices”.

This talk will introduce you to the world of post-quantum cryptography by giving a hands-on tutorial on how its most prominent member - Kyber - works. We'll start with high school level mathematics and work our way up to constructing Kyber. By constructing such a toy-sized Kyber, we can learn how the system works, comprehend its design decisions and see how it is related to an NP-hard problem. After that we’ll take a brief look into how PQC will change real world cryptography in the near future.