Program: here

Abstract: The public-key cryptographic schemes used in practice to secure communications are known to be completely breakable by quantum computers. Although the timeline for building cryptographically-relevant quantum computers remains uncertain, interest in deploying quantum-resistant cryptosystems has surged. Governments worldwide are promoting standards for quantum-safe cryptography, and industry is beginning to integrate quantum-safe cryptography into their products.

In 2024, the U.S. government's National Institute of Standards and Technology (NIST) published standards for lattice-based key encapsulation and signature schemes, as well as for hash-based signatures. Of these standardized schemes, the lattice-based Kyber key encapsulation mechanism (KEM) and the Dilithium signature scheme are seeing the broadest adoption.

This course introduces lattice-based cryptography, focusing on the design and analysis of the Kyber key encapsulation mechanism. Kyber's security is based on the Module Learning With Errors (MLWE) problem, which involves solving noisy linear equations over a polynomial ring. After describing Kyber, I'll explain its connection to lattice problems. I'll then introduce the LLL lattice basis reduction algorithm, a fundamental tool for analyzing hardness of lattice-based cryptosystems.