CSE206A: Lattices Algorithms and Applications (Fall 2025)

Course description

Point lattices are powerful mathematical objects that can be used to efficiently solve many important problems in computer science, most notably in the areas of cryptography and combinatorial optimization. This course gives a general introduction to the theory of point lattices, their algorithms, computational complexity, mathematical techniques, and applications to cryptography. Specific topics touched by the course include:

• Algorithms: approximation algorithms for the efficient solution of lattice approximation problems, exponential time algorithms for the exact solution of NP-hard lattice problems.
• Lattice-based cryptanalysis: using lattice algorithms to break cryptographic functions.
• Computational Complexity: NP-hardness, reductions, connection between average-case and worst-case complexity
• Lattice Based Cryptography: the design of basic cryptographic functions that are as hard to break as solving hard lattice problems.
• Advanced mathematical techniques: Fourier/Harmonic analysis methods for the study of lattice problems. Lattice problems from Algebraic Number Theory and their application to the design of very efficient cryptographic functions.

Prerequisites and Coursework

The main prerequisites for the course are general mathematical maturity, knowledge of basic mathematics (good linear algebra and probability theory, basic abstract algebra, and a little bit of calculus) and introductory level algorithms and complexity theory (mathematical models of computation, analysis of algorithms, polynomial time solvability, NP-hardness, etc.) Some prior knowledge of cryptography is useful, but not required. No prior knowledge of advanced complexity theory, Fourier analysis, or algebraic number theory is assumed, but you should be prepared to learn a bit about all this through the course.

Coursework for students enrolled in the course will include a substantial amount of reading, 4 individual homework assignments, and a team project to be executed in groups of 2 or 3 students. Projects should be discussed with the instructor by the end of the 5th week of classes, and will be due during the 10th week. Each group should submit a written report, and possibly deliver a short presentation.

Homework

Homework assignments will be posted here and submitted through gradescope

• Homework 1
• Homework 2
• Homework 3
• Homework 4

Reading Assignments

The course will be based on a combination of lecture notes, research papers and other online material as posted below. The following links are from the last offering of this course, and may be updated throughout the course.

• Point Lattices: Lattices, Bases, Gram-Schmidt orthogonalization, and Lattice determinant. slides

• Minkowski’s Theorem: The Shortest Vector Problem (SVP) and Minkowski’s Theorems. slides

• PRG Cryptanalysis: Subsetsum and Linear Congruential Generators, and their cryptanalysis

• The LLL Algorithm: The Basis Reduction algorithm of Lenstra, Lenstra and Lovasz. Approximating SVP and CVP with 2^O(n) in polynomial time.

• Duality: The dual lattice and the Closest Vector Problem (CVP)

• Computational Complexity: reductions and NP-hardness

  Reductions between lattice problems:

  • Approximating shortest lattice vectors is not harder than approximating closest lattice vectors (Info. Proc. Letters, 1999)
  • Efficient reductions among lattice problems (SODA 2008)
  • On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem (CRYPTO 2009)

  NP-hardness:

  • The hardness of the closest vector problem with preprocessing (IEEE Trans. IT, 2001)
    Very simple reduction for exact CVP
  • Inapproximability of SVP: toward a deterministic reduction (Theory of Computing 8:(689):487-511 – 2012)
    NP-hardness of SVP, discussing the issue of derandomization
  • Locally Dense Codes
    A simple construction that allows to derandomize a similar NP-hardness proof, but for linear codes
  • SVPp is NP-Hard for all p>2, Even to Approximate Within a Factor of 2^log(1-eps)n
    A very recent paper on deterministic NP-hardness of SVP, but for non-euclidean norm
  • Deterministic Hardness of Approximation of Unique-SVP and GapSVP in Lp norms for p>2
    Another very recent paper on deterministic NP-hardness, but for uSVP, which is equivalent to BDD

• Block basis reduction: improving LLL approximation factor using low dimensional SVP solvers

  • Lecture notes: slides
  • Series of blog posts by former UCSD student Michael Walter
  • Finding short lattice vectors within mordell’s inequality (STOC 2008)
  • Practical, Predictable Lattice Basis Reduction (Eurocrypt 2016)
  • Slide Reduction, Revisited - Filling the Gaps in SVP Approximation (Crypto 2020)

• CVP Algorithms for Special Lattices

  • Linear-time nearest point algorithms for Coxeter lattices (IEEE Trans. Inf. Theory, 2010)
    Efficient CVP algorithm for a family of lattices that includes the A_n and A_n^* lattices discussed in class.
  • Finding a closest point in a lattice of Voronoi’s first kind (SIAM J. Discret. Math.)
    Less efficient (still polynomial time) CVP algorithm for another important class of lattices
  • The closest vector problem in tensored root lattices of type A and in their duals
    Another very intesting polynomial time CVP algorithm for the tensor product of A_n lattices

• Worst-case/Average-case connection:

  • Random Lattices and Lattice Cryptography: Random lattices, the SIS and LWE problems, and construction of basic cryptographic primitives, like one-way functions and collision resistant hashing.

  • Harmonic Analysis lecture notes and slides
    See also Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography (PKC 2020)

  • Average-case Hardness of SIS Lecture notes. Relevant references:

    • Worst-case to average-case reductions based on Gaussian measure (FOCS 2004/SICOMP 2007)
    • Finding the closest lattice vector when it’s unusually close (SODA 2000)
    • Trapdoors for hard lattices and new cryptographic constructions (STOC 2008)

  • For the LWE problem, see

    • On lattices, learning with errors, random linear codes, and cryptography (STOC 2005/JACM 2009)
    • Public-key cryptosystems from the worst-case shortest vector problem (STOC 2009)
    • Classical hardness of learning with errors (STOC 2013)

• Exact algorithms for SVP and CVP

  • Faster exponential time algorithms for the shortest vector problem (SODA 2010), Lecture Notes slides
  • A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations (STOC 2010 / SICOMP 2013) slides
  • Fast Lattice Point Enumeration with Minimal Overhead (SODA 2015)

• Ring Lattices and the Number Theoretic Transform

  • Sorry, no lecture notes. But here is the slides on FFT/NTT from the second lecture
  • SWIFFT: a modest proposal for FFT hashing (FSE 2008)
  • On Ideal Lattices and learning with Errors over Rings

External Links

A collection of Links to papers and other resources on lattice cryptography and algorithms (not very actively) maintained by Daniele Micciancio, mostly for his own personal use.

Introductory chapters and surveys on lattice cryptography:

• Introductory chapter on lattices from “Complexity of Lattice problems: a cryptographic perspective” (2002). The rest of the book is a bit out of date, but still a good introduction to the subject.
• Survey chapter on Lattice-Based Cryptography from “Post Quantum Cryptography” (2009)
• A Decade of Lattice Cryptography. An more recent extensive survey covering most advanced applications of lattices in cryptography.
• Survey chapter on Cryptographic functions from worst-case complexity assumptions from “The LLL Algorithm: Survey and Applications” (2009). The book has many other interesting chapters covering more applications of lattices in computer science and mathematics.
• Tutorial on The Geometry of Lattice Cryptography from FOSAD 2011.
• Survey on The Learning With Errors Problem from CCC 2010.

Other courses’ webpages:

• Oded Regev’s course on Lattices in Computer Science at Tel Aviv university.
• Chris Peikert’s course on Lattices in Cryptography at U. Michigan
• Vinod Vaikuntanathan’s courses on Lattices, Lattices, Learning with Errors and Post-Quantum Cryptography and From Lattices to Program Obfuscation at Berkeley/MIT.

Implementations and Libraries:

The two main libraries implementing the lattice reduction algorithms studied in this course are:

• fpLLL: state of the art impementation of lattice reduction and related algorithms using fast floating point arithmetics.
• Number Theory Library (NTL). A C++ library for lattice basis reduction, polynomial arithmetics and other algebraic problems.
• flatter: a fast, LLL-like lattice reduction algorithm by Nadia Heninger and Keegan Ryan.