1.2 Lattice Basis: Vectors & Matrices

How you describe a lattice — and why the same lattice can look easy or impossibly hard depending on how you describe it.

What Is a Lattice Basis?

A lattice basis is a linearly independent set of vectors whose integer combinations generate every point in a lattice. The basis is not unique: infinitely many different bases can describe exactly the same lattice. A short, nearly orthogonal basis is called good because it makes geometric problems easier to solve.

A lattice is built from a set of directions called basis vectors. Think of them like the axes on a map: once you have your directions, every location on the map can be described by how many steps you take along each axis. Change the axes, and the same locations now have different coordinates — but the terrain itself hasn’t changed.

This is the key idea of this section: the same lattice can be described by many different sets of basis vectors. Some descriptions make the lattice easy to work with. Others make it look completely intractable. That gap is the foundation of lattice cryptography.

Intuition

Imagine giving someone walking directions that reach every intersection in Manhattan. The simplest way is two basic steps: “walk 1 block north” and “walk 1 block east”. These basic steps are your basis vectors.

You could instead give two very different steps: “walk 100 blocks north and 99 east” and “walk 101 blocks north and 100 east”. By combining these forwards and backwards you still reach exactly the same intersections, because 100·100 − 99·101 = 1. Not every pair of big steps works: with “99 north and 100 east” as the second step the determinant would be 199, and most intersections would be missed.

In lattice language, the simple steps are a good basis and the long ones a bad basis. The grid of intersections, the lattice, never changes; only its description does.

The Basis Matrix

Rather than listing basis vectors one at a time, we stack them as columns of a single matrix. This matrix BB compactly encodes the entire shape of the lattice. Any lattice point is obtained by multiplying BB by a column vector of integers.

Definition 2 — Basis Matrix

Write the basis vectors as the columns of a matrix B=[b1∣b2∣⋯∣bn]B = [b_1 \mid b_2 \mid \cdots \mid b_n]. Then the lattice is:

Λ(B)={Bx∣x∈Zn}\Lambda(B) = \{ Bx \mid x \in \mathbb{Z}^n \}

In plain English: take any column of integers xx, multiply it by BB, and you get a lattice point. When the number of basis vectors equals the ambient dimension (a square matrix), we call the lattice full-rank.

Many Bases, One Lattice

Here is something surprising: a lattice has infinitely many valid bases. Consider a 2D lattice built from two vectors. You can swap one basis vector for the sum of both and get a completely different-looking pair of arrows — yet they generate exactly the same infinite grid of points.

The transformations that turn one valid basis into another are called unimodular matrices. They are integer matrices whose determinant is exactly +1 or −1. Multiplying a basis by a unimodular matrix reshuffles the basis vectors without adding or removing any lattice points.

Definition 3 — Equivalent Bases

Two bases BB and B′B' generate the same lattice if and only if B′=BUB' = BU for some integer matrix UU with det⁡(U)=±1\det(U) = \pm 1. Such matrices are called unimodular.

Intuition: UU tells you how to mix the old basis vectors (with integer coefficients, no fractions) to get the new ones. The lattice points don’t move — only the labels change.

Basis explorer: one lattice, many bases

Drag the tips of b₁ and b₂. Then press a basis-change button and watch which things change and which do not.

b₁b₂
‖b₁‖
2.06
‖b₂‖
1.58
|det B| (cell area)
2.75
orthogonality defect
1.19

Drag the handles, or apply a basis change below.

What to notice: Basis changes such as b₂ ← b₂ + b₁ rearrange the arrows and the shaded cell, but every lattice point stays put and the cell’s area |det B| never changes. A long, skewed basis describes exactly the same lattice as a short, nearly orthogonal one. That gap between “bad” and “good” bases is what lattice cryptography is built on.

Good Bases and Bad Bases

Not all bases are equally useful. A good basis has short, nearly perpendicular vectors. Given such a basis, you can quickly find nearby lattice points, estimate the shortest vector, and solve geometric problems efficiently. A bad basis has long, nearly parallel vectors that are highly skewed. The lattice is identical — but working with a bad basis feels like navigating with a wildly distorted map.

Some lattice trapdoor schemes use this asymmetry: a secret, well-behaved basis makes decoding practical, while the public description does not reveal that useful basis. This is one way to build lattice cryptography. ML-KEM and ML-DSA instead use noisy modular equations and short secrets; their public keys are not simply bad bases of a secret lattice.

Gram–Schmidt Orthogonalization

To measure how “skewed” a basis is, we use a classical tool from linear algebra called Gram–Schmidt orthogonalization. The idea: given your basis vectors, iteratively subtract off their projections onto each other to produce a new set of perpendicular vectors. These perpendicular vectors are not a lattice basis (they’re generally not integer combinations of the originals), but they reveal the underlying geometry of the basis.

Definition 4 — Gram–Schmidt Vectors

Start with b~1=b1\tilde{b}_1 = b_1. For each subsequent vector, subtract its projection onto all previous orthogonal vectors:

b~i=bi−∑j<i⟨bi,b~j⟩∥b~j∥2⋅b~j\tilde{b}_i = b_i - \sum_{j < i} \frac{\langle b_i, \tilde{b}_j \rangle}{\|\tilde{b}_j\|^2} \cdot \tilde{b}_j

The resulting vectors b~1,…,b~n\tilde{b}_1, \dots, \tilde{b}_n are mutually perpendicular. Their lengths measure how much each basis vector contributes in a “fresh” direction not already covered by previous vectors. Short Gram–Schmidt vectors mean a skewed basis; long ones mean a well-spread basis.

An important fact: the product of all Gram–Schmidt lengths always equals ∣det⁡(B)∣|\det(B)|, the volume of the fundamental cell of the lattice. So the total volume is fixed — what changes between bases is how evenly that volume is distributed across the Gram–Schmidt vectors.

The LLL Algorithm: Taming a Bad Basis

If you are given a bad basis, can you find a better one? Yes — the LLL algorithm (named after Lenstra, Lenstra, and Lovász, 1982) does exactly this in polynomial time. It won’t find the best possible basis (that problem is as hard as SVP), but it finds one that is provably pretty good — short enough to be useful, efficient enough to run on large inputs.

What LLL guarantees

After running LLL, the first basis vector b1b_1 satisfies ∥b1∥≤2(n−1)/2⋅λ1\|b_1\| \leq 2^{(n-1)/2} \cdot \lambda_1 (for the standard parameter δ=3/4\delta = 3/4), where λ1\lambda_1 is the true shortest vector length. In dimension 100, this worst-case bound allows an output about 249.5≈10152^{49.5} \approx 10^{15}× longer than the true shortest vector. In practice LLL does far better, typically finding a vector only about 1.02n≈91.02^{n} \approx 9× longer than det⁡(Λ)1/n\det(\Lambda)^{1/n} — good enough for many applications, not good enough to break well-designed lattice cryptography.

BKZ: stronger reduction

Block Korkine-Zolotarev (BKZ) is a family of algorithms that improve on LLL by solving SVP inside overlapping blocks of the basis. Larger block size β\beta gives shorter output vectors but runs exponentially slower in β\beta. BKZ with a large block size β\beta is the main tool in lattice cryptanalysis — used to estimate how hard a lattice problem actually is.

The trapdoor construction

In GPV signatures and similar schemes, the signer holds a short basis SS (the trapdoor). The public key is a related long basis A=SUA = SU. Signing uses SS to solve CVP efficiently; verification only needs the public AA. Without SS, solving CVP under AA is believed computationally infeasible.

The Dual Lattice

Every lattice has a companion called its dual lattice. The dual contains all vectors that have integer inner products with every vector in the original lattice. If the original lattice is “big” (coarsely spaced), the dual is “small” (finely spaced), and vice versa. The dual lattice appears in the security proofs of LWE and in the analysis of Gaussian distributions over lattices, which we will encounter in §2.2.

Definition 5 — Dual Lattice

Λ∗={y∈Rn∣⟨y,x⟩∈Z for all x∈Λ}\Lambda^* = \{ y \in \mathbb{R}^n \mid \langle y, x \rangle \in \mathbb{Z} \text{ for all } x \in \Lambda \}

If BB is a basis for Λ\Lambda, then (B−⊤)(B^{-\top}) is a basis for Λ∗\Lambda^*. The determinant of the dual is det⁡(Λ∗)=1/det⁡(Λ)\det(\Lambda^*) = 1/\det(\Lambda) — confirming that a denser lattice has a sparser dual, and vice versa.

For a complete calculation of the inverse-transpose basis and a two-dimensional example, see the dual lattice guide.

The Gram Matrix

Given a basis matrix BB, the Gram matrix is the symmetric positive definite matrix G=B⊤BG = B^\top B. Its entries are all pairwise inner products of the basis vectors: the diagonal entry Gii=∥bi∥2G_{ii} = \|b_i\|^2 is the squared length of the ii-th basis vector, and the off-diagonal entry Gij=⟨bi,bj⟩G_{ij} = \langle b_i, b_j \rangle measures how much vectors ii and jj point in the same direction.

The Gram matrix encodes the complete metric geometry of the basis — all lengths and angles — in a single object. If Gij=0G_{ij} = 0 for all i≠ji \neq j, the basis is perfectly orthogonal. The determinant of the Gram matrix gives the squared volume of the fundamental parallelepiped:

Gram Matrix — Key Formula

For a basis matrix BB with columns b1,…,bnb_1, \dots, b_n:

G=B⊤B,Gij=⟨bi,bj⟩G = B^\top B, \qquad G_{ij} = \langle b_i, b_j \rangle
det⁡(Λ)=det⁡(G)=∣det⁡(B)∣\det(\Lambda) = \sqrt{\det(G)} = |\det(B)|
The angle θij\theta_{ij} between basis vectors satisfies cos⁡θij=Gij/GiiGjj\cos\theta_{ij} = G_{ij} / \sqrt{G_{ii} G_{jj}}. A basis is orthogonal if and only if GG is diagonal. Two bases BB and B′B' generate the same lattice if and only if their Gram matrices are related by G′=U⊤GUG' = U^\top G U for a unimodular integer matrix UU.

Volume of a Lattice

The volume (or determinant) of a lattice is one of its most fundamental invariants. It measures the “density” of lattice points: a small volume means points are close together; a large volume means they are sparsely distributed. Crucially, the volume does not depend on which basis you choose — it is an intrinsic property of the lattice itself.

Lattice Volume — Definition and Properties

For any basis matrix BB of Λ\Lambda:

vol(Λ)=det⁡(Λ)=∣det⁡(B)∣\mathrm{vol}(\Lambda) = \det(\Lambda) = |\det(B)|
This equals the volume of the fundamental parallelepiped spanned by the basis vectors. It is invariant under basis change: if B′=BUB' = BU with det⁡(U)=±1\det(U) = \pm 1, then ∣det⁡(B′)∣=∣det⁡(B)∣⋅∣det⁡(U)∣=∣det⁡(B)∣|\det(B')| = |\det(B)| \cdot |\det(U)| = |\det(B)|.

For the integer lattice Zn\mathbb{Z}^n: vol(Zn)=1\mathrm{vol}(\mathbb{Z}^n) = 1.
For a scaled lattice cΛc\Lambda: vol(cΛ)=cn⋅vol(Λ)\mathrm{vol}(c\Lambda) = c^n \cdot \mathrm{vol}(\Lambda).
For the dual: vol(Λ∗)=1/vol(Λ)\mathrm{vol}(\Lambda^*) = 1/\mathrm{vol}(\Lambda).

The product of Gram–Schmidt norms also equals the volume: vol(Λ)=∏i=1n∥b~i∥\mathrm{vol}(\Lambda) = \prod_{i=1}^n \|\tilde{b}_i\|, which is how the volume is efficiently computed in practice.

Change of Basis and Unimodular Matrices

Since a lattice has infinitely many valid bases, it is important to characterize precisely when two matrices BB and B′B' generate the same lattice. The answer is short: they are related by a unimodular matrix — an integer matrix with determinant ±1\pm 1.

Unimodular Matrices and Basis Equivalence

An integer matrix U∈Zn×nU \in \mathbb{Z}^{n \times n} is unimodular if det⁡(U)=±1\det(U) = \pm 1. Equivalently, UU is invertible over the integers — its inverse U−1U^{-1} also has integer entries.

Λ(B)=Λ(B′)  ⟺  B′=BU for some unimodular U\Lambda(B) = \Lambda(B') \iff B' = BU \text{ for some unimodular } U
The set of all n×nn \times n unimodular matrices forms a group under multiplication, denoted GLn(Z)\mathrm{GL}_n(\mathbb{Z}). The elementary row and column operations over integers — adding an integer multiple of one row to another, or swapping two rows — all produce unimodular matrices.

In cryptography, a trapdoor consists of a short basis SS and a unimodular matrix UU such that B=SUB = SU is a bad (long, skewed) public basis. Anyone who sees only BB cannot recover SS without solving the lattice reduction problem.

Check Your Understanding

  1. Q1. You replace basis vector b₂ with b₁ + b₂ and keep b₁. What happens to the lattice?

  2. Q2. In a basis-based trapdoor scheme, why keep a “good” basis private?

  3. Q3. Which quantity is the same no matter which basis you use to describe a lattice?

  4. Q4. A lattice is spread out, with points far apart (large volume). What does its dual lattice look like?