Lattices.io — Mathematical Lattices & Post-Quantum Cryptography

Not all lattices are created equal. Certain lattices appear repeatedly in mathematics, physics, and cryptography because they have exceptional properties: maximum packing density, deep algebraic symmetry, or computational structures that make them useful. This section surveys the most important lattice families — concrete examples that ground the abstract theory.

The Integer Lattice ℤⁿ

The simplest lattice of all is the standard integer lattice $\mathbb{Z}^n$ : all points in $$n$$ -dimensional space with integer coordinates. Its basis is the identity matrix $$I_n$$ , its determinant is 1, and its shortest vector has length 1. Every other lattice can be thought of as a "deformation" of $\mathbb{Z}^n$ by an invertible linear map.

Properties of ℤⁿ

$\det(\mathbb{Z}^n) = 1$ (unit fundamental cell)
$\lambda_1 = 1$ (all coordinate unit vectors have length 1)
$\lambda_1 = \lambda_2 = \cdots = \lambda_n = 1$ (all successive minima equal)
$\mu = \sqrt{n}/2$ (covering radius: the corner of the unit cube)

Self-dual: $(\mathbb{Z}^n)^\vee = \mathbb{Z}^n$ . The integer lattice is its own dual. This makes it the natural setting for modular arithmetic over integers — the foundation of LWE.

The Root Lattices: Aₙ and Dₙ

Root lattices arise from the classification of semisimple Lie algebras. They are the "next simplest" lattices after $\mathbb{Z}^n$ and have important applications in sphere packing, error-correcting codes, and algebraic number theory.

The Aₙ lattice

$A_n \subset \mathbb{Z}^{n+1}$ : the set of integer vectors $(x_0, \dots, x_n)$ summing to zero.

In dimension 2: $$A_2$$ is the hexagonal lattice — the densest 2D sphere packing. Its kissing number is 6 (each point has 6 nearest neighbors).

$\det(A_n) = n+1$ , $\lambda_1 = \sqrt{2}$ .

The Dₙ lattice

$D_n \subset \mathbb{Z}^n$ : integer vectors whose coordinates sum to an even number.

$$D_4$$ is the densest 4D packing; $$D_4$$ has 24 minimal vectors (kissing number 24). $$D_n$$ is the "checkerboard lattice" — alternating occupied and empty unit cubes.

$\det(D_n) = 4$ , $\lambda_1 = \sqrt{2}$ .

The E₈ Lattice

$$E_8$$ is arguably the most remarkable mathematical object in this field. It is the unique densest lattice packing in 8 dimensions, proven optimal by Maryna Viazovska in 2016 (Fields Medal, 2022). It has extraordinary symmetry: 240 minimal vectors (the "roots"), a kissing number of 240, and deep connections to modular forms, string theory, and the Monster group.

Definition 23 — The E₈ Lattice

$$E_8$$ can be defined as the set of vectors $(x_1, \dots, x_8) \in \mathbb{R}^8$ such that either:

— All $x_i \in \mathbb{Z}$ and $\sum x_i \equiv 0 \pmod{2}$ , or
— All $x_i \in \mathbb{Z} + 1/2$ and $\sum x_i \equiv 0 \pmod{2}$ .

Key properties:
$\det(E_8) = 1$ (self-dual: $E_8^\vee = E_8$ )
$\lambda_1 = \sqrt{2}$ , kissing number 240
Hermite ratio: $\lambda_1^2/\det^{2/8} = 2$ , achieving $\gamma_8 = 2$
Packing density: $\pi^4/384 \approx 0.2537$ — provably optimal in 8D.

The 240 minimal vectors of $$E_8$$ are exactly the roots of the exceptional Lie algebra $$E_8$$ , which appears in superstring theory. The lattice has automorphism group of order $$696{,}729{,}600$$ . It is the only even unimodular lattice in dimension 8.

The Leech Lattice Λ₂₄

In dimension 24, the Leech lattice plays the role $$E_8$$ plays in dimension 8 — and then some. It is the densest known 24-dimensional packing (proven optimal by Viazovska et al. 2016), has a kissing number of $$196{,}560$$ , and its automorphism group is directly related to the Monster group — the largest sporadic simple group in group theory.

Key Properties of Λ₂₄

$\det(\Lambda_{24}) = 1$ (even unimodular)
$\lambda_1 = 2$ (shortest vectors have length 2)
Kissing number: $$196{,}560$$
Packing density: $\pi^{12}/479001600$ — optimal in 24D.

The Leech lattice can be constructed as the unique even unimodular lattice in dimension 24 with no vectors of length $\sqrt{2}$ . Its automorphism group $\mathrm{Co}_0$ (Conway's group) has order $$8{,}315{,}553{,}613{,}086{,}720{,}000$$ .

NTRU Lattices

The NTRU lattice is the algebraic lattice underlying the NTRU cryptosystem (1996) — the oldest lattice-based cryptosystem that remains secure. Unlike the geometric lattices above, NTRU lattices have a specific structure derived from polynomial rings.

Definition 24 — NTRU Lattice

In NTRU with ring $R = \mathbb{Z}[x]/(x^n - 1)$ and modulus $$q$$ , the public key is a polynomial $h = g \cdot f^{-1} \pmod{q}$ where $$f, g$$ are small polynomials. The NTRU lattice is:

$\Lambda_h = \{ (u, v) \in R^2 : u \equiv hv \pmod{q} \}$

Its basis matrix is a $2n \times 2n$ circulant block matrix. The short vector $$(f, g)$$ is hidden in this lattice; recovering it is the NTRU problem. The Falcon signature scheme (FIPS 206) is built on NTRU lattices.

Cyclotomic Lattices and Ring-LWE

Ring-LWE and Module-LWE operate over rings of integers in cyclotomic number fields. The ring $\mathbb{Z}[x]/(x^n + 1)$ (with $$n$$ a power of 2) is the ring of integers in the cyclotomic field $\mathbb{Q}(\zeta_{2n})$ , where $\zeta_{2n}$ is a primitive $$2n$$ -th root of unity.

Elements of this ring correspond to lattice points in $\mathbb{R}^n$ via the canonical embedding, and the ring structure induces a rich algebraic symmetry on the resulting lattice — called an ideal lattice. Every ideal in the ring corresponds to a sublattice, and the structure enables efficient arithmetic via NTT.

Ideal lattices

A lattice $\Lambda$ is an ideal lattice if it corresponds to an ideal in a number ring. It is closed under the ring's multiplication action: if $v \in \Lambda$ , then all cyclic rotations of $$v$$ are also in $\Lambda$ . This structure makes ideal lattices more efficient (NTT multiplication) but potentially more vulnerable to algebraic attacks than general lattices.

Module lattices

A module lattice is a direct sum of ideal lattices. Kyber and Dilithium use module lattices of rank $$k$$ — $$k$$ copies of an ideal lattice arranged as a vector. This interpolates between general LWE lattices (rank 1 is Ring-LWE; rank $$n$$ is close to plain LWE) and provides a more conservative hardness assumption than Ring-LWE alone.

q-ary Lattices: The Lattices Behind Cryptographic Hard Problems

The lattices that actually appear in LWE and SIS hardness are called q-ary lattices. They are the most practically important family for post-quantum cryptography.

Definition 25 — q-ary Lattice

For a matrix $A \in \mathbb{Z}_q^{m \times n}$ and modulus $$q$$ , define the two q-ary lattices:

$\Lambda_q(A) = \{ y \in \mathbb{Z}^m : y = Ax \pmod{q} \text{ for some } x \in \mathbb{Z}^n \}$

$\Lambda_q^\perp(A) = \{ y \in \mathbb{Z}^m : Ay = 0 \pmod{q} \}$

SIS asks for a short nonzero vector in $\Lambda_q^\perp(A)$ ; LWE asks to find the close lattice point to a target in $\Lambda_q(A)$ . These two lattices are duals of each other (up to scaling by $$q$$ ), which is why SIS and LWE are mathematically dual hard problems.