Lattice Metrics: Successive Minima to 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.

Intuition

A house is described by its floor area, ceiling height and number of rooms. A lattice is described by a few numbers too: how far apart the closest points are ( $\lambda_1$ ), how much space one cell takes up (the determinant), and how skewed a particular basis is (the Hadamard ratio).

These numbers are how cryptographers compare lattices and bases, and several of them feed directly into security estimates.

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_0$ 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_0 = \left( \frac{\|b_1\|}{\det(\Lambda)^{1/n}} \right)^{1/n}$

Equivalently, $\|b_1\| = \delta_0^n \cdot \det(\Lambda)^{1/n}$ . (Some papers use the exponent $1/(n-1)$ instead; for large $n$ the difference is negligible, and this site uses $1/n$ throughout.) The value of $\delta_0$ achieved by BKZ- $\beta$ reduction is approximately $\delta_0 \approx \left( \frac{\beta}{2\pi e} \, (\pi\beta)^{1/\beta} \right)^{1/(2(\beta-1))}$ for block sizes $\beta \gtrsim 50$ . Cryptographic parameters are chosen so that the $\delta_0$ an attack needs (around 1.003–1.004 for the NIST lattice standards) is too expensive to reach for any adversary.

The root Hermite factor is the single most important number for estimating lattice security. Given $\delta_0$ and $n$ , you can compute the block size $\beta$ needed to achieve that $\delta_0$ , and from $\beta$ you compute the number of operations needed. Kyber is designed so that achieving the necessary $\delta_0$ 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: ρ ≤ μ, with μ tied to λₙ

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). But $\mu$ is not bounded by any multiple of $\rho$ : for the basis $(1,0), (0,1000)$ , $\rho = 1/2$ while $\mu \approx 500$ . The right comparison is with the last successive minimum: $\lambda_n/2 \leq \mu \leq (\sqrt{n}/2) \cdot \lambda_n$ . 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^* \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 $\eta_\varepsilon(\Lambda)$ 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 $\Lambda$ and $\varepsilon > 0$ , the smoothing parameter is the smallest Gaussian width $s$ such that the discrete Gaussian restricted to the dual lattice is small:

$\eta_\varepsilon(\Lambda) = \min\left\{ s > 0 : \rho_{1/s}(\Lambda^* \setminus \{0\}) \leq \varepsilon \right\}$
where $\rho_s(S) = \sum_{v \in S} e^{-\pi \|v\|^2 / s^2}$ is the Gaussian mass (the same convention as §9, so $\rho_{1/s}(S) = \sum_{v \in S} e^{-\pi s^2 \|v\|^2}$ ). Its key consequence: for $s \geq \eta_\varepsilon(\Lambda)$ , a continuous Gaussian of width $s$ reduced modulo $\Lambda$ is within statistical distance $\varepsilon/2$ of uniform over a fundamental domain.

Role in LWE security proofs: The worst-case to average-case reduction for LWE (Regev 2005) requires sampling a discrete Gaussian $D_{\Lambda, s}$ over the lattice with width $s \geq \eta_\varepsilon(\Lambda)$ . 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 (Micciancio–Regev 2004): $\eta_\varepsilon(\Lambda) \leq \sqrt{\ln(2n(1+1/\varepsilon))/\pi} \cdot \lambda_n(\Lambda)$ , which ties the smoothing parameter directly to the longest successive minimum of the lattice itself.

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_{\Lambda,s}$ assigns to each lattice point $v \in \Lambda$ a probability proportional to the continuous Gaussian evaluated at $v$ .

Discrete Gaussian Distribution $D_{\Lambda,s}$

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

$\rho_s(x) = e^{-\pi \|x\|^2 / s^2}$
The Gaussian mass of the lattice is:

$\rho_s(\Lambda) = \sum_{v \in \Lambda} \rho_s(v) = \sum_{v \in \Lambda} e^{-\pi \|v\|^2 / s^2}$
The discrete Gaussian distribution assigns probability:

$D_{\Lambda,s}(v) = \frac{\rho_s(v)}{\rho_s(\Lambda)} = \frac{e^{-\pi \|v\|^2 / s^2}}{\sum_{w \in \Lambda} e^{-\pi \|w\|^2 / s^2}}$
When $s \geq \eta_\varepsilon(\Lambda)$ , sampling from $D_{\Lambda,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 $\rho_s(\Lambda)$ to $\rho_{1/s}(\Lambda^*)$ :

$\rho_s(\Lambda) = \frac{s^n}{\det(\Lambda)} \cdot \rho_{1/s}(\Lambda^*)$
This duality between a lattice and its dual is the technical foundation of Regev’s reduction.

For a numerical example of the distribution above and its use in cryptography, read the discrete Gaussian sampling guide.

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 $\Lambda$ with packing radius $\rho = \lambda_1/2$ is:

$\Delta(\Lambda) = \frac{V_n \cdot \rho^n}{\det(\Lambda)} = \frac{V_n \cdot (\lambda_1/2)^n}{\det(\Lambda)}$
where $V_n = \pi^{n/2}/\Gamma(n/2+1)$ is the volume of the unit ball. The sphere packing problem asks: what is the maximum possible $\Delta$ ?

The connection to Hermite’s constant is direct: $\Delta(\Lambda) = V_n \cdot \left(\frac{\lambda_1}{2 \det(\Lambda)^{1/n}}\right)^n \leq V_n \cdot \left(\frac{\sqrt{\gamma_n}}{2}\right)^n$
Record packing densities (proven optimal):

— Dimension 2 ( $A_2$ , hexagonal): $\Delta = \pi/\sqrt{12} \approx 0.9069$
— Dimension 8 ( $E_8$ ): $\Delta = \pi^4/384 \approx 0.2537$
— Dimension 24 (Leech lattice $\Lambda_{24}$ ): $\Delta = \pi^{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.

Check Your Understanding

Q1. Which of these numbers describes the basis you happen to be using, rather than the lattice itself?
Q2. An attacker runs BKZ and gets an output vector with root Hermite factor δ₀ = 1.010. A stronger run reaches δ₀ = 1.005. What does the lower δ₀ mean?
Q3. A public key basis has a Hadamard ratio close to 0. What does that tell you?
Q4. Why does the smoothing parameter matter for LWE security proofs?

← Previous1.3Geometry of Numbers Next →1.5Lattice ReductionThe art of finding shorter, better bases.

Unfamiliar symbol? The math reference explains the notation used across the site.

Found a mistake or something unclear? Report it on GitHub or email hello@ovasylenko.com.