Lattice Metrics — Norms, Distances, and Covering Radius

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.

Beginner's Intuition 💡

Just like you might describe a house by its square footage, the height of its ceilings, and the number of rooms, mathematicians describe lattices using specific numbers called metrics.

Instead of looking at the whole infinite grid, we look at these stats: "What's the distance between the closest dots?" ($\lambda_1$), "How skewed is the grid?" (Hadamard ratio), or "How much volume does one cell take up?" (Determinant). These numbers tell us everything we need to know to figure out if a lattice is secure enough to use in modern cryptography.

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.

8. The Smoothing Parameter η_ε(Λ) and LWE Security

The smoothing parameter $η_{ε} (Λ)$ was introduced by Micciancio and Regev (2004) and is one of the most important technical tools in lattice cryptography. It marks the threshold at which a discrete Gaussian distribution over a lattice "looks" continuous — the point beyond which the lattice's discrete structure is statistically undetectable.

Definition — Smoothing Parameter

For a lattice $Λ$ and $ε > 0$ , the smoothing parameter is the smallest Gaussian width $s$ such that the discrete Gaussian restricted to the dual lattice is small:

$η_{ε} (Λ) = min {s > 0 : ρ_{1/ s} (Λ^{\lor} ∖ {0}) \leq ε}$
where $ρ_{r} (S) = \sum_{v \in S} e^{- π r^{2} ∥ v ∥^{2}}$ is the Gaussian mass. Equivalently, it is the smallest $s$ such that a Gaussian of width $s$ over $Λ$ is within statistical distance $ε /2$ of a continuous Gaussian.

Role in LWE security proofs: The worst-case to average-case reduction for LWE (Regev 2005) requires sampling a discrete Gaussian $D_{Λ, s}$ over the lattice with width $s \geq η_{ε} (Λ)$ . Below this threshold, the samples reveal information about the lattice structure; above it, they are statistically safe. The reduction shows: if you can solve LWE efficiently, you can solve GapSVP in the worst case — but only if the noise parameter exceeds the smoothing parameter.

A useful bound: $η_{ε} (Λ) \leq ln (2 n / ε) / π \cdot λ_{n} (Λ^{\lor})$ , which ties the smoothing parameter directly to the longest successive minimum of the dual lattice.

9. Gaussian Measures on Lattices

Discrete Gaussian distributions over lattices are the key tool for generating lattice-based signatures and for the security reductions in LWE. The discrete Gaussian $D_{Λ, s}$ assigns to each lattice point $v \in Λ$ a probability proportional to the continuous Gaussian evaluated at $v$ .

Discrete Gaussian Distribution $D_{Λ, s}$

The Gaussian function centered at the origin with width $s$ is:

$ρ_{s} (x) = e^{- π ∥ x ∥^{2} / s^{2}}$
The Gaussian mass of the lattice is:

$ρ_{s} (Λ) = v \in Λ \sum ρ_{s} (v) = v \in Λ \sum e^{- π ∥ v ∥^{2} / s^{2}}$
The discrete Gaussian distribution assigns probability:

$D_{Λ, s} (v) = \frac{ρ _{s} ( v )}{ρ _{s} ( Λ )} = \frac{e ^{- π ∥ v ∥^{2} / s^{2}}}{\sum _{w \in Λ} e ^{- π ∥ w ∥^{2} / s^{2}}}$
When $s \geq η_{ε} (Λ)$ , sampling from $D_{Λ, s}$ is statistically close to sampling from a continuous Gaussian and rounding — making it safe for use in security proofs. The Poisson summation formula relates $ρ_{s} (Λ)$ to $ρ_{1/ s} (Λ^{\lor})$ :

$ρ_{s} (Λ) = \frac{s ^{n}}{det ( Λ )} \cdot ρ_{1/ s} (Λ^{\lor})$
This duality between a lattice and its dual is the technical foundation of Regev's reduction.

10. Packing Density and Sphere Packing Records

The packing density of a lattice measures what fraction of space is covered by non-overlapping balls centered at lattice points. It is one of the oldest and most studied problems in mathematics.

Packing Density — Definition and Records

The packing density of a lattice $Λ$ with packing radius $ρ = λ_{1} /2$ is:

$Δ (Λ) = \frac{V _{n} \cdot ρ ^{n}}{det ( Λ )} = \frac{V _{n} \cdot ( λ _{1} /2 ) ^{n}}{det ( Λ )}$
where $V_{n} = π^{n /2} /Γ (n /2 + 1)$ is the volume of the unit ball. The sphere packing problem asks: what is the maximum possible $Δ$ ?

The connection to Hermite's constant is direct: $Δ (Λ) = V_{n} \cdot (\frac{λ _{1}}{2 det ( Λ ) ^{1/ n}})^{n} \leq V_{n} \cdot (\frac{γ _{n}}{2})^{n}$
Record packing densities (proven optimal):

— Dimension 2 ( $A_{2}$ , hexagonal): $Δ = π / 12 \approx 0.9069$
— Dimension 8 ( $E_{8}$ ): $Δ = π^{4} /384 \approx 0.2537$
— Dimension 24 (Leech lattice $Λ_{24}$ ): $Δ = π^{12} /479001600 \approx 0.00193$

For $n = 2, 8, 24$ , these are proven to be the global optima over all packings (not just lattice packings), established by Thue (n=2), Viazovska (n=8, 2016), and Cohn–Kumar–Miller–Radchenko–Viazovska (n=24, 2016). For all other dimensions, the optimal packing density is unknown.

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.