Lattice

This post traces the path from the Lindner–Peikert cryptosystem — an early LWE-based encryption scheme with provable correctness and CPA security — through the polynomial ring underlying lattice cryptography, where multiplication turns into a structured matrix operation and coefficient sizes stay tightly controlled, to Module-LWE (MLWE), a generalization of LWE that remains as hard as ordinary LWE despite its extra structure. Building on MLWE, Kyber-PKE achieves an extremely low decryption failure rate and provable CPA security, and after ciphertext compression per the FIPS 203 standard, is upgraded via the Fujisaki–Okamoto transform into Kyber-KEM (ML-KEM) — NIST’s standardized, chosen-ciphertext-secure, plaintext-aware key encapsulation mechanism. [Read More]

An introduction to the Learning With Errors (LWE) problem, its lattice structure, hardness reduction from BDD and SVP, and its computational variants: DLWE and ss-LWE. [Read More]

This post, Part 8 of the Cryptography series, dives into the foundations of lattice-based cryptography. We begin by defining lattices, their bases, and crucial invariant properties like the determinant and successive minima. The post also analyzes the core NP-Hard computational problems on lattices, including the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). Finally, we explore the LLL (Lenstra–Lenstra–Lovász) algorithm, a foundational basis reduction algorithm that finds approximate solutions to these problems in polynomial time. [Read More]