Lattice Basis Reduction

Learning outcomes

On successful completion of this course, students will:

  1. Understand the relevant mathematics background in linear algebra and lattice theory.
  2. Understand the LLL lattice basis algorithm.
  3. Appreciate the wide range of applications of LLL in cryptanalysis.
Note to instructors

If you are teaching a course in applied cryptography and would like to use my video lectures as a secondary source or a primary source, please send me an email message. I will be happy to arrange a meeting with you, to tell you about my experience teaching applied cryptography over the past 30 years, and we can have a discussion about the curriculum, exercises, projects, and tests for your course. If you use any of the resources (videos or slides) on this web page in your classes, please do provide your students a link to my page (cryptography101.ca).


YouTube Lectures

Full Playlist

V5: Cryptographic applications

V6: LLL improvements


Additional Material

Errata (last updated: January 9, 2026)

Here is a list of errors in the video lectures. These errors have already been corrected in the lecture slides (available below).

  • Slide 23 (V1): The fastest quantum algorithm known for solving SVP has running time 2^{0.2563n+o(n)} (see https://eprint.iacr.org/2022/676).
  • Slide 24 (V1): The volume of a rank-m lattice L(B) should be \sqrt(\det(B^T*B)) instead of \sqrt(\det(B*B^T)). Note that B^T*B is an mxm matrix.
  • Slide 58 (V4): Third last line: Delete “\leq min_i {2^{i-1} ||b_i^*||^2} \leq 2^{n-1} \lambda_1(L)^”
Lecture slides

NEW: Lecture notes
LLL example