Lattice-Based Cryptography

Cryptographic systems based on hard mathematical problems involving lattices. The foundation of most post-quantum standards.

Lattice-based cryptography builds cryptographic primitives from computationally hard problems on mathematical lattices. It’s the basis for the primary post-quantum cryptography standards.

What’s a Lattice?

A lattice is a regular grid of points in $n$-dimensional space, generated by integer combinations of basis vectors:

$$\mathcal{L}=\{a_1{\vec{v}}_1+a_2{\vec{v}}_2+\dots +a_n{\vec{v}}_n:a_i\in \mathbb{Z}\}$$

Think of it as an infinite, regular arrangement of points in space.

Hard Problems

Learning With Errors (LWE)

Given noisy linear equations over a ring: $$b_i=⟨{\vec{a}}_i,\vec{s}⟩+e_i(\mathrm{mod}q)$$

Find the secret $\vec{s}$ given many $({\vec{a}}_i,b_i)$ pairs. The noise $e_i$ is small but makes solving hard.

Ring-LWE

LWE over polynomial rings. More efficient and used in practice.

Module-LWE

A middle ground between LWE and Ring-LWE.

Short Integer Solution (SIS)

Find a short non-zero vector in the null space of a matrix.

Shortest Vector Problem (SVP)

Find the shortest non-zero vector in a lattice. Believed hard even for quantum computers.

Why Lattices for PQC?

NIST Standards

ML-KEM (Kyber)

• Type: Key Encapsulation Mechanism
• Based on: Module-LWE
• Use: Key exchange

ML-DSA (Dilithium)

• Type: Digital signature
• Based on: Module-LWE + Module-SIS
• Use: Authentication

FN-DSA (Falcon)

• Type: Digital signature
• Based on: NTRU lattices
• Use: Compact signatures

Key Sizes

Lattice schemes have larger keys than classical:

Larger but manageable for most applications.

Beyond Encryption

Lattices enable advanced cryptography:

• Fully Homomorphic Encryption (FHE): Compute on encrypted data
• Attribute-Based Encryption: Access control via attributes
• Functional Encryption: Controlled function evaluation

Security Levels

NIST defines security levels:

See also: Post-Quantum Cryptography, Quantum-Safe, Shor’s Algorithm