Lecture 10 · Thursday 23 October 2025

Lattices, Short Integer Solution (SIS), Learning with Errors (LWE) and trapdoors

The course leaves the groups of Chapters 2 and 3 and moves to lattices. One lecture supplies the threat model, the geometry, the two average-case assumptions, the ring variants, the first primitives and the trapdoor that makes them usable.

Deck: 04_Crypto_101_PQC.pdf Chapter 4 Sections 1 to 6

Before ThisWhere Lecture 9 Left Off

Lecture 9 closed the key-exchange arc of Chapter 3: HKDF (HMAC-based key derivation function) in extract-then-expand form turned Diffie-Hellman shared secrets into session keys, password-authenticated key exchange derived secrets from low-entropy passwords and TLS (Transport Layer Security) 1.3 was read as the deployed instance of the preceding theory. The lecture ended the classical part of the course with one unstated premise still in place: factoring and discrete logarithms remain hard. Lecture 10 removes that premise.

This LectureWhat It Adds

This lecture replaces the broken assumptions with a new hard-problem family. It begins with Shor's algorithm and the operational reasons for migrating now: harvested ciphertexts, retroactive forgeries and deployment latency. It then defines lattices, bases, unimodular equivalence, determinants, successive minima and Minkowski's bound, because every later construction is a statement about short vectors in a lattice with a bad public basis. Short Integer Solution (SIS) and Learning with Errors (LWE) follow as the average-case problems, connected to worst-case geometry by Ajtai, Regev and Peikert. The lecture then moves LWE into polynomial rings and modules to make keys and ciphertexts practical, derives one-way functions, collision-resistant hashes and commitments from SIS and ends with trapdoors: short bases and the MP12 (Micciancio-Peikert 2012) gadget construction that let a key holder invert SIS and LWE instances while everyone else sees a hard problem.

Study PlanWhat to Read, in Lecture Order

  1. Chapter 4 §1: The quantum threat. Shor's algorithm, harvesting, retroactive forgery, deployment latency and the asymmetric effect of Grover on symmetric keys.
  2. §2: Lattices, bases and geometry. Definitions, unimodular equivalence, determinant, successive minima and Minkowski. The stage shows why a bad basis hides short vectors.
  3. §3: Short Integer Solution (SIS) and Learning with Errors (LWE). Definitions, worst-case reductions and the residual test for an LWE secret. Run the LWE lab with noise on and off.
  4. §4: Ring-LWE and Module-LWE. The dimension knobs $d$ and $k$, the Fast Fourier Transform (FFT)-style speedup and the security caveat for ideal lattices.
  5. §5: SIS primitives. One-way function, compression hash, commitment and the leftover hash lemma used later by Regev and GSW (Gentry, Sahai and Waters).
  6. §6: Trapdoors and Gaussian sampling. Babai nearest-plane, the gadget matrix, MP12 (Micciancio-Peikert 2012) and the perturbation method. Run the Closest Vector Problem (CVP) lab on both bases.

PracticeExercises for This Lecture