Lattices.io — Mathematical Lattices & Post-Quantum Cryptography

We now have the basic vocabulary of lattices. The next step is to quantify their properties precisely. A lattice metric is a number that captures some aspect of a lattice's geometry — how dense it is, how short its shortest vector is, how well-shaped its basis is. These metrics appear everywhere in lattice cryptography: in parameter selection, security proofs, cryptanalysis, and algorithm analysis.

This section builds up a catalogue of the most important metrics. Each one answers a specific question about the lattice, and together they give a complete quantitative picture.

1. The Gram Matrix and Determinant

The simplest question about a lattice is: how is it shaped? The Gram matrix encodes the complete geometric information about a basis — all the lengths and angles — in one matrix of numbers.

Definition 7 — Gram Matrix

Given a basis $$B$$ , the Gram matrix is:

$G = B^\top B$

The entry $G_{ij} = \langle b_i, b_j \rangle$ is the dot product of basis vectors $$i$$ and $$j$$ . The diagonal entries are the squared lengths $\|b_i\|^2$ ; the off-diagonal entries measure how aligned pairs of vectors are. If all off-diagonal entries were zero, the basis would be perfectly orthogonal.

The lattice determinant is $\det(\Lambda) = \sqrt{\det(G)}$ . This is the volume of the fundamental tile — the same for every basis of the same lattice.

2. Successive Minima: λ₁ through λₙ

We met the successive minima in §1.3. They are the most fundamental length invariants of a lattice. Recall: $\lambda_k$ is the smallest radius of a ball that contains $$k$$ linearly independent lattice vectors. In practice:

λ₁ — Shortest vector

The length of the shortest nonzero lattice vector. This is the central quantity in SVP. Finding it exactly requires exponential time in general; it cannot be computed efficiently even with a quantum computer. All lattice security parameters are chosen to make $\lambda_1$ hard to find.

λ₂, ..., λₙ — Higher minima

$\lambda_2$ is the length of the shortest vector not parallel to the first; and so on. A large gap between $\lambda_1$ and $\lambda_2$ means the shortest vector is uniquely shorter than all others — which matters for the uniqueness of decryption in LWE-based encryption.

Minkowski's constraint

The successive minima are not independent: their product is bounded by the determinant. More precisely, $\lambda_1 \cdot \lambda_2 \cdots \lambda_n \leq \gamma_n^{n/2} \cdot \det(\Lambda)$ . You can't have all of them be simultaneously large in a dense lattice.

3. Hermite's Constant γₙ

How short can the shortest lattice vector be, relative to the overall density of the lattice? The answer is captured by Hermite's constant $\gamma_n$ — the best possible ratio of shortest-vector-length to lattice-spacing, optimized over all lattices in dimension $$n$$ .

Definition 8 — Hermite's Constant

$\gamma_n$ is the largest possible value of $\lambda_1^2 / \det(\Lambda)^{2/n}$ over all lattices in $$n$$ dimensions. Equivalently, for any lattice:

$\lambda_1(\Lambda) \leq \sqrt{\gamma_n} \cdot \det(\Lambda)^{1/n}$

Known values: $\gamma_2 = 2/\sqrt{3} \approx 1.15$ (hexagonal lattice), $\gamma_8 = 2$ (the E₈ lattice — the densest known 8D packing), $\gamma_{24} = 4$ (the Leech lattice). Asymptotically, $\gamma_n \approx n/(2\pi e)$ .

Lattices achieving the Hermite bound are the "most efficient" possible — they pack the most points into the least space. The E₈ lattice and the Leech lattice are the famous examples in dimensions 8 and 24, whose optimality was only proven in 2016–2017.

4. The Hadamard Ratio — Measuring Basis Orthogonality

This metric answers: how close to perpendicular are our basis vectors? If all basis vectors were perfectly orthogonal (at right angles to each other), the parallelepiped they span would have maximum volume for its edge lengths. Any skewing reduces the volume. The ratio of actual volume to maximum possible volume is the Hadamard ratio.

Definition 9 — Hadamard Ratio

$\mathcal{H}(B) = \left( \frac{|\det(B)|}{\|b_1\| \cdot \|b_2\| \cdots \|b_n\|} \right)^{1/n}$

This is always between 0 and 1.
— Value = 1: perfect orthogonal basis. Volume equals the product of lengths.
— Value near 0: highly skewed basis. Long, nearly-parallel vectors that largely cancel out.

A good lattice basis has a Hadamard ratio close to 1. A "hard" public key in a trapdoor scheme has a Hadamard ratio close to 0 — it looks terrible but still generates the same lattice.

5. The Root Hermite Factor δ

When a lattice reduction algorithm outputs a short vector, we want to measure how good that output is. The root Hermite factor $\delta$ is the standard measure used in cryptanalysis. It compares the length of the output vector to the "expected" lattice spacing, normalized by dimension.

Definition 10 — Root Hermite Factor

If a reduction algorithm outputs a vector of length $\|b_1\|$ from a lattice with determinant $\det(\Lambda)$ in dimension $$n$$ , the root Hermite factor is:

$\delta = \left( \frac{\|b_1\|}{\det(\Lambda)^{1/n}} \right)^{1/n}$

Equivalently, $\|b_1\| = \delta^n \cdot \det(\Lambda)^{1/n}$ . The value of $\delta$ achieved by BKZ- $\beta$ reduction is approximately $\delta \approx (\beta / 2\pi e)^{1/(2\beta)}$ . Typical cryptographic parameters target $\delta \leq 1.005$ being too expensive to reach for any adversary.

The root Hermite factor is the single most important number for estimating lattice security. Given $\delta$ and $$n$$ , you can compute the block size $\beta$ needed to achieve that $\delta$ , and from $\beta$ you compute the number of operations needed. Kyber is designed so that achieving the necessary $\delta$ requires at least $2^{128}$ operations.

6. Covering and Packing Radii

Packing radius ρ

$\rho = \lambda_1 / 2$ . The largest ball centered at a lattice point that doesn't overlap any other lattice ball. Think of it as the "personal space" of each lattice point. Maximizing the packing density (fraction of space covered) is the sphere packing problem — one of the oldest problems in mathematics.

Covering radius μ

$\mu = \max_{t} \min_{v \in \Lambda} \|t - v\|$ . The farthest any point in space can be from its nearest lattice point. In cryptography, this is the maximum possible CVP distance. LWE decryption works because errors are smaller than $\lambda_1/2$ , which guarantees a unique closest lattice point to decode.

The gap: ρ ≤ μ ≤ n·ρ

The covering radius is always at least the packing radius (you must go at least $\rho$ to reach a lattice point from the worst position) and at most $n \cdot \rho$ (by Banaszczyk's transference theorem). Lattices where $\mu \approx \rho$ are nearly "perfect" — every point is almost equidistant from its nearest lattice neighbor.

7. The Smoothing Parameter

The final metric in our catalogue is the most technically advanced — but also one of the most important for understanding why LWE security proofs work. The smoothing parameter tells you how wide a Gaussian distribution over the lattice needs to be before it "looks" continuous — before the discrete structure of the lattice becomes invisible.

Definition 11 — Smoothing Parameter

The smoothing parameter $\eta_\varepsilon(\Lambda)$ is the smallest Gaussian width $$s$$ such that when you sample from a Gaussian of width $$s$$ restricted to the lattice, the result is statistically indistinguishable (up to error $\varepsilon$ ) from a continuous Gaussian.

Formally, it is the smallest $$s$$ such that the "dual Gaussian mass" on nonzero dual lattice points is small: $\sum_{v \in \Lambda^\vee \setminus 0} e^{-\pi s^2 \|v\|^2} \leq \varepsilon$ .

Why it matters: in the reduction from worst-case SVP to average-case LWE, we need to sample from a discrete Gaussian over the lattice in a way that doesn't leak information about which lattice is being used. The smoothing parameter is precisely the threshold above which this is safe.

All Metrics at a Glance

Gram matrix G

Encodes all pairwise inner products of basis vectors. Captures the full geometry of the basis. Determinant gives the lattice volume.

Successive minima λ₁ ≤ ... ≤ λₙ

How short the shortest, second-shortest, ..., longest "necessary" vectors are. The key measure of lattice point density. Basis-independent.

Hermite constant γₙ

The best possible λ₁ relative to det¹/ⁿ. Achieved by the densest known lattice packings in each dimension.

Hadamard ratio H(B)

How orthogonal the basis is. 1 = perfect; near 0 = highly skewed. Measures basis quality, not the lattice itself.

Root Hermite factor δ

Output quality of a reduction algorithm. The key parameter for estimating how many operations an attacker needs.

Smoothing parameter ηε

Minimum Gaussian width to "blur" the discrete lattice structure. The threshold for worst-case to average-case security reductions.