Lecture 11 · Tuesday 28 October 2025

Falcon, Crystals-Dilithium and Crystals-Kyber

The trapdoor machinery of Lecture 10 becomes two published NIST standards and one forthcoming standard: ML-DSA signatures, ML-KEM key encapsulation and FN-DSA signatures based on Falcon.

Deck: 04_Crypto_101_PQC.pdf (post-quantum cryptography) Chapter 4 Sections 7 to 10

Before ThisWhere Lecture 10 Left Off

Lecture 10 set up the post-quantum foundation. Shor's algorithm ended factoring and discrete logarithms as long-term assumptions. Lattices supplied the geometry, SIS (Short Integer Solution) and LWE (Learning With Errors) supplied the average-case assumptions tied to worst-case problems by reductions, and ring and module variants supplied the efficiency needed for deployment. SIS alone gave a one-way function, a compression hash and a commitment. The lecture ended with the missing ingredient, the trapdoor: a short basis, or the MP12 (Micciancio-Peikert) gadget equivalent, that makes selected SIS and LWE instances easy for the key holder and hard for everyone else.

This LectureWhat It Adds

This lecture applies the trapdoor to NIST's two published lattice standards, ML-DSA and ML-KEM, and to Falcon, which NIST selected for the forthcoming FN-DSA standard. Falcon signs by hashing the message to a target and sampling a short SIS (Short Integer Solution) preimage with the trapdoor; verification checks the equation and the norm, and forgery is inhomogeneous SIS. The sampler must hide the trapdoor, which is why the perturbation method matters. Crystals-Dilithium takes the identification route: a three-move protocol made non-interactive by Fiat-Shamir, repaired for lattices by repetition, smallness checks and rejection sampling. Regev encryption then builds Secure Against Chosen-Plaintext Attacks (CPA-secure) public-key encryption from LWE (Learning With Errors) by encoding a bit at half the modulus, and the Fujisaki-Okamoto transform converts it into a Secure Against Chosen-Ciphertext Attacks (CCA-secure) Key Encapsulation Mechanism (KEM) by derandomizing, checking by re-encryption and hashing the recovered message into the key. Crystals-Kyber is the standardized instantiation, deployed in hybrid mode with an elliptic-curve exchange. FIPS (Federal Information Processing Standards) 203 and 204 record the standards.

Study PlanWhat to Read, in Lecture Order

  1. Chapter 4 §7: Falcon. Hash-to-target, Gaussian preimage sampling, the shortness check and why sampler leakage breaks the scheme.
  2. §8: Canonical identification and Crystals-Dilithium. Fiat-Shamir, special soundness (two accepting transcripts reveal the witness), Honest-Verifier Zero Knowledge (HVZK), the three lattice failures and rejection sampling.
  3. §9: Regev public-key encryption. Construction, cancellation proof, the Learning with Errors (LWE) and leftover hash lemma hybrids plus the dual and LP11 (Lindner-Peikert 2011) variants. Step through the stage.
  4. §10: Fujisaki-Okamoto and Crystals-Kyber. Transforms T and U (the two steps of the Fujisaki-Okamoto transform), the re-encryption check, explicit rejection and the Module-Lattice Key Encapsulation Mechanism (ML-KEM) instantiation.

PracticeExercises for This Lecture