Course: Intro to Lattice Algorithms and Cryptography
Time: Tuesdays, 2pm-4:45pm (Week 6-21)
Location: Utrecht University, Buys-Ballotgebouw, Room 023

Course Description:

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.

Grading Scheme:

Homework assignments (3x): 40%
Final Exam: 60%

Instructors:

Daniel Dadush: dadush@cwi.nl.
Leo Ducas: leo.ducas@cwi.nl.

News:

Homeworks:

Schedule:

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
  • Lecture notes: N/A.
12. 24/04 Applications of LLL
  • Lecture notes: N/A.
13. 01/05 Worst-case to average reduction Part I
  • Lecture notes: N/A.
14. 08/05 Worst-case to average reduction: Part II
  • Lecture notes: N/A.
15. 15/05 Fully Homomorphic Encryption
  • Lecture notes: N/A.
16. 22/05 AKS Sieving Algorithm for SVP
  • Lecture notes: N/A.

Other Lattice Courses: