Overview of the course:

Lattices have been at the core of most of the recent advances in cryptography, such as efficient postquantum cryptography or computation over encrypted data. The goal of this class is to cover some fundamental notions of lattices in cryptography, from the mathematical and algorithmics aspects of lattices to first cryptographic constructions.

We will cover the following topics:

  • Fondations: mathematics of lattices
  • Algorithmics for lattice problems: how to solve approximate-SVP
  • SIS and LWE from hardness to first constructions
  • Trapdoor for hard lattice problems
  • Fully-Homomorphic Encryption

Course Notes:

  • Class 1: notes
    • Definitions: lattice, basis, rank, dimension, span, determinant
    • Gram-Schmidt Orthogonalization
    • Successive minima
    • Minkowski's convex body, first, and second theorems
  • Class 2: notes
    • Shortest Vector Problem and its variants
    • Complexity landscape of SVP
    • LLL algorithm
    • Enumeration algorithm
    • BKZ algorithm
  • Class 3: notes
    • SIS problem
    • Hardness of SIS and typical parameters
    • Ajtai's collision-resistant hash function
    • Schnorr's discrete log-based signature and Lyubashevsky's SIS-based signature
  • Class 4: notes
    • LWE: SIS in the planted regime
    • Typical parameters and noise distributions
    • Left-over hash lemma
    • Regev's primal and dual public-key encryption
  • Class 5: notes
    • Lattice trapdoors
    • Trapdoor one-way functions
    • GPV signatures
    • Gaussian sampling
    • GPV identity-based encryption
  • Class 6: notes
    • Homomorphic encryption
    • Examples of partially-homomorphic encryption
    • GSW fully homomorphic encryption
    • Bootstrapping