The geometry and structure of Euclidean lattices has been studied for centuries to understand the geometry of periodic structures such as dense packings of spheres. Much more recently, lattices have been central in designing cryptographic schemes that are believed much more secure than number theoretic schemes such as RSA, which are compromised if efficient quantum computers are ever built.
The aim of this course is to provide a solid understanding of the geometry of lattices, algorithms for solving central computational problems on lattices, and their applications to lattice based cryptography. Sample topics include: Minkowski's First & Second Theorems, transference theorems in the geometry of numbers, algorithms for the Shortest (SVP) & Closest Vector Problems (CVP), Learning with Errors (LWE), Regev's LWE based public key cryptography scheme, Lattice based signatures, NTRU, Worst-case to average case reductions, and Discrete Gaussian sampling.
| Date | Topic | Resources |
|---|
| 1. 06/02 | Lattices and Bases |
|
| 2. 13/02 | Determinants, Packing and Covering and Minkowski Theorems |
|
| 3. 20/02 | Two Square Theorem, Gram Schmidt Orthogonalization and
Babai's Fundamental Domain |
|
| 4. 27/02 | Babai's Nearest Plane and the LLL Algorithm |
|
| 5. 06/03 | Properties of LLL bases, Duality, Enumeration Algorithms |
|
| 6. 13/03 | Transference Theorems, HKZ Bases, Poisson Summation Formula |
|
| 7. 20/03 | Periodic Gaussian, Discrete Gaussian and Transference |
|
| 8. 27/03 | End of Transference, Complexity of Lattice Problems |
|
| 9. 03/04 | Short Integer Solution (SIS) problem, Collision
resistant functions, One way functions |
|
| 10. 10/04 | Smoothness of SIS, Commitment schemes from SIS |
|
| 11. 17/04 | Learning with Errors and Public Key Encryption |
|
| 12. 24/04 | Applications of LLL |
|
| 13. 01/05 | Worst-case to average reduction Part I |
|
| 14. 08/05 | Worst-case to average reduction: Part II |
|
| 15. 15/05 | Fully Homomorphic Encryption |
|
| 16. 22/05 | AKS Sieving Algorithm for SVP |
|
