Lattice Cryptography Explorer

What you should be able to explain by the end

The big picture

Classical public-key cryptography often relies on integer factoring or discrete logarithms. A sufficiently capable quantum computer running Shor’s algorithm would threaten those assumptions. Lattice-based systems instead build security from problems involving high-dimensional geometric or algebraic structures for which no comparably devastating quantum algorithm is known.

A recurring teaching idea in this tutorial is simple: linear algebra is easy; linear algebra with carefully chosen uncertainty can be hard. LWE turns that intuition into a rigorous cryptographic problem.

What is a lattice?

A lattice is an infinite, regularly repeating set of points obtained by taking integer combinations of basis vectors. In two dimensions, choose two linearly independent vectors b₁ and b₂. Every lattice point has the form:

The same lattice can have many different bases. A “nice” basis may consist of short, nearly orthogonal vectors; an awkward basis can consist of long, skewed vectors. This difference between an easy description and a difficult-looking description helps build intuition for lattice cryptography.

Which lattice problems are supposed to be hard?

Why quantum resistance is plausible

Shor’s algorithm exploits special algebraic structure in factoring and discrete logarithms. No known quantum algorithm solves the lattice problems used by modern lattice cryptography with a similar exponential-to-polynomial collapse. “Post-quantum” therefore means designed around problems currently believed to resist both classical and quantum attacks; it does not mean mathematically proven invulnerable.

Learning With Errors: linear equations plus tiny mistakes

Suppose a secret value is s. If an attacker sees many exact modular equations of the form b = a·s mod q, recovering s is usually straightforward. LWE changes the equation by adding a small random error:

Each sample is almost consistent with the same secret, but not exactly. In the real problem, s, a, and e are vectors (or structured vectors of polynomials), and the dimension is large.

Three related flavors

What is a KEM?

A key-encapsulation mechanism is not normally used to encrypt an entire file directly. Its job is to let two parties agree on a fresh shared secret over a public channel. That secret then feeds a symmetric cipher or authenticated-encryption scheme.

FrodoKEM: “plain” LWE with large matrices

FrodoKEM is designed around comparatively conservative algebraic structure: rather than using polynomial-ring structure for its main LWE computation, it works with large matrices over modular integers. That makes the connection to plain LWE especially direct, at the cost of larger keys/ciphertexts and heavier matrix arithmetic than highly structured schemes.

Mini matrix laboratory

The following uses tiny 3×3 matrices and tiny numbers so you can see every operation. This is a teaching model only.

What to remember

• FrodoKEM is an excellent teaching example for seeing the connection between matrix algebra and LWE noise.
• It deliberately avoids the same degree of algebraic structure exploited for efficiency in ring/module schemes.
• That design choice changes engineering tradeoffs; it does not mean “structure is insecure.” Modern structured schemes are parameterized and analyzed specifically around their chosen assumptions.

NTRU: small polynomials, modular rings, and convolution

NTRU predates the modern LWE family and has its own long line of analysis. Its arithmetic is built from polynomials with small coefficients in a quotient ring. Instead of multiplying ordinary integers or matrices, the algorithm repeatedly multiplies polynomials and reduces them by a polynomial relation and by an integer modulus.

Polynomial convolution lab

Enter coefficient lists for two degree-<7 polynomials. The demo multiplies them using cyclic convolution (the behavior created by reducing by x⁷−1), then reduces coefficients mod q.

NTRU and the NIST process

NTRU reached the third-round finalist stage of NIST’s post-quantum standardization process. NIST ultimately standardized CRYSTALS-Kyber as the initial lattice-based KEM rather than NTRU. NTRU remains important historically, academically, and in continuing standardization and implementation work outside that specific NIST selection.

CRYSTALS: Kyber → ML-KEM, Dilithium → ML-DSA

CRYSTALS-Kyber is the submission from which NIST’s ML-KEM standard was derived. CRYSTALS-Dilithium is a related lattice-based signature design from which NIST’s ML-DSA was derived. One establishes keys; the other signs data. Do not mix their roles.

Module-LWE in one picture

ML-KEM works with short vectors of polynomials rather than one giant ordinary matrix or a single polynomial. Its base polynomial ring is:

At a conceptual level, a public value again resembles a noisy linear map:

But now entries of A, s, e, and t are polynomials in R_q. ML-KEM uses fast polynomial arithmetic, including number-theoretic-transform techniques, to make these operations efficient.

Interactive miniature module demo

Real ML-KEM polynomials have 256 coefficients. This toy version uses four coefficients so you can watch the algebra. It uses negacyclic reduction, corresponding to x⁴ = −1.

The three standardized ML-KEM parameter sets

Side-by-side comparison

Three common misconceptions

Why migration matters before a large quantum computer exists

An adversary can collect encrypted traffic today and attempt to decrypt it later if cryptanalytic capabilities improve. This “harvest now, decrypt later” risk is most important for information that must remain confidential for many years. Migration also takes time because cryptography is embedded in protocols, certificates, hardware, firmware, key-management systems, and compliance processes.

Interactive laboratory checklist

Use the controls in the earlier modules, then record your answers. The browser stores completion locally on this device.

Optional implementation lab with Open Quantum Safe

If students have a separate development machine, the Open Quantum Safe liboqs project provides a common API for experimenting with post-quantum KEMs and signatures. Use it as a prototyping/learning environment and follow the project’s current algorithm-status notes rather than assuming every experimental algorithm is production-ready.

Knowledge check

Glossary

Authoritative and useful external sources

The links below are intentionally weighted toward standards bodies, algorithm-team specifications, peer-reviewed/ePrint papers, and maintained implementation projects.

Standards and NIST project material

FrodoKEM

NTRU

CRYSTALS / Kyber / Dilithium

Lattice foundations and deeper reading