Lattice-based cryptography is the study of cryptosystems whose security is based on the hardness of solving computational problems from lattices. Compared to traditional public-key cryptosystems based on the hardness of factoring integers or computing discrete logarithms, cryptosystems from lattices typically offer a combination of advantages: conjectured resistance against quantum computers, provable security from well-known worst-case assumptions and asymptotic efficiency. Moreover, lattices also provide a rich toolbox for designing advanced cryptographic primitives, some of which have not been known to be achievable based on the factoring and the discrete logarithm problems. Having these appealing features, lattice-based cryptography has become a main direction in modern cryptography research.

This course aims to cover a few topics in lattice-based cryptography. The course is divided into two parts. In the first part, we will recall some necessary background on lattices, and study variants of the two prominent average-case problems used in lattice-based cryptography, Short Integer Solution (SIS) and Learning With Errors (LWE), as well as basic cryptosystems from SIS and LWE, including one-way functions, collision-resistant hash functions and public-key encryption schemes. In the second part, we will discuss several important tools and techniques used in lattice-based cryptography, and the designs of advanced systems such as trapdoor-based signatures, identity-based encryption, fully-homomorphic encryption, ring/group signatures and e-cash.