Abstract:

Cryptography aims to efficiently secure communication and computation against powerful adversaries. The past 50 years have seen great efforts to place cryptography on solid mathematical ground through rigorous security models and proofs of security. This “provable security” perspective has become the cornerstone of modern cryptography. Various mathematical objects (which found their original motivation elsewhere) have been fundamental tools in the design of secure cryptographic protocols. Of particular note, computational problems on point lattices and linear error-correcting codes form the basis of “post-quantum” cryptography — protocols which are believed to resist attacks by quantum computers — and linear codes are used to design cryptographic protocols with unconditional security (a.k.a. information-theoretic security) for a plethora of important tasks.

The main goal of this mini-course is to give an overview of applications of point lattices and linear codes to post-quantum and information-theoretic cryptography. Another goal is to entice more people with strong mathematical background to join the cryptography community in analyzing the mathematical problems that power most of the cryptography that we use (or will use in the near future) and in identifying ways in which other mathematical objects can be exploited to develop improved cryptographic protocols.

We will start by introducing basic concepts in cryptography. Then, we will discuss some of the most important mathematical problems underlying post-quantum cryptography, including why we care about them and how they are related to lattices and codes. Finally, we will see applications of linear codes to information-theoretic cryptography. A more detailed tentative program follows below.

No background is required beyond basic algebra, combinatorics, and probability. Some mathematical maturity is a plus.