Chapter 7: Lattices for programmers

A lattice is the set of integer combinations of a basis. Fix $n$ linearly independent vectors $b_1, \ldots, b_n$ in $\mathbb{R}^n$ and the lattice $L(B)$ is the set of all sums $c_1 b_1 + \cdots + c_n b_n$ with integer coefficients $c_i \in \mathbb{Z}$. The basis $B$ is a presentation of the lattice; the lattice is the object the presentation names. In dimension at least two, the same lattice has infinitely many different bases; in dimension one, $a\mathbb{Z}$ admits only $a$ and $-a$ as bases.

Every lattice-based scheme in Part II rests on a claim about the lattice as an object. The shortest nonzero vector is hard to find, a noisy version of the closest vector is hard to find, or the lattice carries enough structure that a fast transform is available. The geometric quantities in this chapter, determinant, dual, successive minima, SVP, and CVP, are properties of the lattice rather than of a particular basis (Micciancio & Goldwasser, 2002). Cryptographic instances still come with representations: a public basis may be hard to use, a trapdoor basis may make sampling or decoding easy, and the ring or module representations of Chapter 9 expose the fast arithmetic used by schemes such as ML-KEM. Chapter 7 builds the algebra that makes the basis-invariant side precise: bases over $\mathbb{Z}$, change of basis, the determinant, the dual lattice, and Minkowski’s bound on how short the shortest vector can be.

A lattice two ways

Consider the 2D lattice $L \subset \mathbb{R}^2$ with basis vectors $b_1 = (3, 1)$ and $b_2 = (1, 2)$. Writing these as the columns of a 2-by-2 integer matrix gives the basis

$$B_1 = \begin{pmatrix} 3 & 1 \\ 1 & 2 \end{pmatrix}.$$

Every point in $L(B_1)$ is of the form $B_1 x$ for some integer vector $x \in \mathbb{Z}^2$. The integer combinations $(3, 1)$, $(1, 2)$, $(4, 3) = b_1 + b_2$, and $(2, -1) = b_1 - b_2$ all sit in $L$. The vector $(1, 0)$ does not: solving $B_1 x = (1, 0)$ gives $x_1 = 2/5$ and $x_2 = -1/5$, which are not integers.

Now fix a second basis

$$B_2 = \begin{pmatrix} 3 & 4 \\ 1 & 3 \end{pmatrix}$$

with columns $b'_1 = (3, 1)$ and $b'_2 = (4, 3)$. The claim is that $L(B_1)$ and $L(B_2)$ are the same lattice. The quick argument is that $(4, 3) = 1 \cdot b_1 + 1 \cdot b_2$ sits in $L(B_1)$, and $(1, 2) = 1 \cdot b'_2 - 1 \cdot b'_1$ sits in $L(B_2)$. Every basis vector on each side is an integer combination of the other side’s basis vectors, so the two lattices share their generating sets and are equal.

The reader can check this in Python:

import numpy as np

# A lattice in Z^2, stored as its basis B with columns b_1, b_2.
B1 = np.array([[3, 1], [1, 2]], dtype=np.int64)
B2 = np.array([[3, 4], [1, 3]], dtype=np.int64)

def lattice_point(B, x):
    return tuple(int(a) for a in B @ np.asarray(x, dtype=np.int64))

print("b_1  =", lattice_point(B1, [1, 0]))
# ==> b_1  = (3, 1)
print("b_2  =", lattice_point(B1, [0, 1]))
# ==> b_2  = (1, 2)
print("b'_2 =", lattice_point(B2, [0, 1]))
# ==> b'_2 = (4, 3)
print("b_1 + b_2 (in L(B1)) =", lattice_point(B1, [1, 1]))
# ==> b_1 + b_2 (in L(B1)) = (4, 3)

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch07/, one file per block. Appendix C covers the clone and the environment they run on.

The two bases generate the same set. The next section names the algebraic structure underlying this equality. The matrix $U$ with $B_2 = B_1 U$ is an integer matrix with determinant $\pm 1$, called a unimodular matrix, and any two bases of the same lattice are related by some such $U$.

The algebra

Basis over $\mathbb{Z}$

A basis of a full-rank lattice $L \subset \mathbb{R}^n$ is a set of $n$ linearly independent vectors $b_1, \ldots, b_n$ in $\mathbb{R}^n$ such that every element of $L$ is a unique integer combination of the $b_i$. The skeleton of this definition matches Chapter 2’s basis over a field $\mathbb{F}_p$: $n$ independent vectors that span every element of the structure exactly once. The important difference is that the coefficients come from $\mathbb{Z}$, not from a field (Micciancio & Goldwasser, 2002).

$\mathbb{Z}$ is a commutative ring with identity but not a field, so “basis over $\mathbb{Z}$” means something strictly more restricted than “basis over $\mathbb{Q}$ or $\mathbb{R}$”. The restriction shows up as soon as the reader tries to rescale a basis vector. Over $\mathbb{R}$, any nonzero multiple of $b_1$ generates the same line; over $\mathbb{Z}$, only $\pm b_1$ does. The vector $2 b_1$ generates the strict sublattice of even-coefficient combinations and has index 2 in the original lattice (Micciancio & Goldwasser, 2002). This is the narrower meaning of basis that Chapter 2 forward-pointed to.

Unimodular change of basis

An $n$-by-$n$ integer matrix $U$ is unimodular when its determinant is $\pm 1$. Equivalently, $U$ is unimodular when both $U$ and $U^{-1}$ are integer matrices, which follows from the adjugate formula $U^{-1} = \mathrm{adj}(U) / \det(U)$ applied to an integer $U$ (Micciancio & Goldwasser, 2002). The group of unimodular matrices is denoted $\mathrm{GL}_n(\mathbb{Z})$.

The central theorem of this section is that two bases generate the same lattice exactly when they are related by a unimodular change of basis.

Theorem (basis equivalence). Let $B_1, B_2 \in \mathbb{R}^{n \times n}$ be two full-rank matrices. Then $L(B_1) = L(B_2)$ if and only if there exists a unimodular matrix $U \in \mathrm{GL}_n(\mathbb{Z})$ with $B_2 = B_1 U$ (Micciancio & Goldwasser, 2002).

The proof fits in two paragraphs. Suppose first that $B_2 = B_1 U$ for some unimodular $U$. Every column of $B_2$ is then an integer combination of the columns of $B_1$ (the coefficients are the columns of $U$, which are integers), so $L(B_2) \subseteq L(B_1)$. The reverse inclusion follows by writing $B_1 = B_2 U^{-1}$ and observing that $U^{-1}$ is also an integer matrix because $U$ is unimodular.

Conversely, suppose $L(B_1) = L(B_2)$. Every column of $B_2$ sits in $L(B_1)$, so there is an integer matrix $U$ with $B_2 = B_1 U$. Running the same argument with the roles of $B_1$ and $B_2$ swapped produces an integer matrix $V$ with $B_1 = B_2 V$, hence $B_1 = B_1 U V$ and $U V = I$. Taking determinants of $U V = I$ gives $\det U \cdot \det V = 1$. Both factors are integers, so each is $\pm 1$. So $U$ is unimodular.

Concretely, the change-of-basis matrix for the two bases above is

$$U = B_1^{-1} B_2 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix},$$

with $\det U = 1$. So $U$ is unimodular and the claim that $B_1$ and $B_2$ generate the same lattice is formally correct.

The determinant and the fundamental parallelepiped

The determinant of a full-rank lattice $L$ is defined by $\det(L) = |\det B|$ for any basis $B$ of $L$. Basis-invariance follows from the equivalence theorem: if $B_2 = B_1 U$ with unimodular $U$, then $\det B_2 = \det B_1 \cdot \det U = \pm \det B_1$, and taking absolute values gives $|\det B_2| = |\det B_1|$. So $\det(L)$ is a property of $L$ alone, not of the choice of basis (Micciancio & Goldwasser, 2002).

The determinant has a geometric interpretation. The fundamental parallelepiped of a basis $B$ is the half-open region

$$\mathcal{P}(B) = \{B x : 0 \leq x_i < 1 \text{ for all } i\}.$$

Its $n$-dimensional volume is $\int_{[0,1]^n} |\det B| \, dx = |\det B|$ by the Jacobian of the linear map $x \mapsto B x$, so $\det(L)$ is the volume of the fundamental parallelepiped of any basis (Micciancio & Goldwasser, 2002). An equivalent way to think about this: $\det(L)$ is the amount of $\mathbb{R}^n$-volume per lattice point. A lattice with a small determinant is dense, and a lattice with a large determinant is sparse.

The running example has $\det B_1 = 3 \cdot 2 - 1 \cdot 1 = 5$, so $\det(L) = 5$. Every fundamental parallelepiped of $L$ has area $5$, regardless of which basis the reader uses to draw it.

Figure 7.1 shows $L$ with $b_1$ and $b_2$ drawn as arrows and the fundamental parallelepiped shaded.

Figure 7.1. The 2D lattice $L$ with basis $b_1 = (3, 1)$ and $b_2 = (1, 2)$. Lattice points are integer combinations of the basis. The shaded parallelogram is the fundamental parallelepiped $\mathcal{P}(B)$ of area $\det(L) = 5$. Half-open translates of $\mathcal{P}(B)$ by lattice vectors tile the plane, and the tiling has exactly one lattice point per tile.

The interior of the fundamental parallelepiped contains no lattice point. Half-open translates of $\mathcal{P}(B)$ by lattice vectors tile the plane with exactly one lattice point per tile. Closing the parallelogram on every side would double-count boundary points.

The dual lattice

Given a full-rank lattice $L \subset \mathbb{R}^n$, the dual lattice is

$$L^* = \{y \in \mathbb{R}^n : \langle y, x \rangle \in \mathbb{Z} \text{ for all } x \in L\}.$$

For a lattice with basis $B$, the dual is itself a full-rank lattice, and a basis for it is given by $B^{-T} = (B^{-1})^T$ (Micciancio & Goldwasser, 2002). The derivation is two lines. A vector $y$ sits in $L^*$ exactly when $\langle y, B k \rangle = (B^T y)^T k$ is an integer for every $k \in \mathbb{Z}^n$. Evaluating the condition at $k = e_1, \ldots, e_n$ shows that every entry of $B^T y$ is an integer, so $B^T y \in \mathbb{Z}^n$, which is equivalent to $y = B^{-T} z$ for $z = B^T y \in \mathbb{Z}^n$.

Two facts about the dual matter in the rest of Part II. First, the dual-of-dual identity $(B^{-T})^{-T} = B$ gives $L^{**} = L$. The double dual returns the original lattice. Second, when $B$ is an integer matrix, the dual basis $B^{-T}$ is generally rational rather than integer, so $L^*$ need not sit inside $\mathbb{Z}^n$ even when $L \subseteq \mathbb{Z}^n$. The special case $L = \mathbb{Z}^n$ is self-dual, and every other full-rank $L \subseteq \mathbb{Z}^n$ acquires fractional dual vectors: $L \subseteq \mathbb{Z}^n$ forces $\mathbb{Z}^n \subseteq L^*$, while $\det(L^*) = 1/\det(L) < 1$ rules out $L^* \subseteq \mathbb{Z}^n$. The dual lives in the same real span as $L$ but at a different scale. Chapter 9 uses the dual lattice to state the Ring-LWE and Module-LWE hardness assumptions; Chapter 7 supplies the definition, the computational identity, and nothing more. Pontryagin duality and the algebraic dual $\mathrm{Hom}(L, \mathbb{Z})$ are out of scope.

Successive minima and Minkowski’s bound

The successive minima of a full-rank lattice $L$ are a sequence of real numbers

$$\lambda_1(L) \leq \lambda_2(L) \leq \cdots \leq \lambda_n(L).$$

The value $\lambda_i(L)$ is the smallest real $r$ such that $L$ contains $i$ linearly independent vectors of Euclidean norm at most $r$. So $\lambda_1(L)$ is the length of the shortest nonzero vector in $L$, and $\lambda_n(L)$ is the smallest radius that captures $n$ linearly independent lattice vectors (Micciancio & Goldwasser, 2002).

Minkowski’s theorem (first bound). For every full-rank lattice $L \subset \mathbb{R}^n$,

$$\lambda_1(L) \leq \sqrt{n} \cdot \det(L)^{1/n}.$$

This is the form of Minkowski’s bound cited throughout the rest of this book (Micciancio & Goldwasser, 2002). The proof applies Minkowski’s convex body theorem to a suitably scaled centrally symmetric convex body, such as a cube, and then converts the resulting coordinate bound into the Euclidean norm bound. The full argument is out of scope here. Micciancio and Goldwasser give it in full (Micciancio & Goldwasser, 2002). What matters downstream is the algorithmic gap the bound leaves open, which Chapter 13 takes up.

Minkowski’s bound is an existence statement: it guarantees that a short vector is present in $L$, but it does not identify which one. Finding the shortest vector, or finding a vector within a factor $\gamma$ of $\lambda_1(L)$, is the shortest vector problem and its approximate variant, stated later in this chapter.

The four shortest nonzero lattice vectors of the running example are $\pm b_2 = \pm(1, 2)$ and $\pm(2, -1) = \pm(b_1 - b_2)$, all of length $\sqrt{5}$, and no lattice vector is shorter. The argument is a finite case check on the Gram matrix

$$B_1^T B_1 = \begin{pmatrix} 10 & 5 \\ 5 & 5 \end{pmatrix},$$

which gives $\|i\,b_1 + j\,b_2\|^2 = 10 i^2 + 10 i j + 5 j^2$. The nine values over $|i|, |j| \leq 1$ attain minimum nonzero value $5$ exactly at $(i, j) \in \{(0, \pm 1), \pm(1, -1)\}$. Whenever $|i| \geq 2$ or $|j| \geq 2$, the form is at least $10$, so no lattice vector is shorter than $\sqrt{5}$. This gives $\lambda_1(L) = \sqrt{5}$, comfortably below Minkowski’s bound $\sqrt{10} \approx 3.162$ (Micciancio & Goldwasser, 2002).

Building a lattice in Python

The full implementation with a pytest suite lives at solutions/ch07-lattices/. The snippets below show the core idea of each operation in numpy.

Floating point is a toy-size convenience here

These snippets use floating-point linear algebra (np.linalg.solve, np.linalg.det, np.linalg.inv) because the matrices are 2-by-2 with single-digit entries, where rounding back to integers is unambiguous. Lattice membership, determinants, and unimodularity are exact integer or rational questions, so teaching tests should use exact arithmetic (fractions.Fraction, sympy.Matrix, or integer adjugate formulas) once examples grow beyond toy size. Concrete ML-KEM code is different again: it works with modular polynomial arithmetic in $R_q = \mathbb{Z}_q[x]/(x^n + 1)$, not with floating-point inverses of large real matrices.

Start with the lattice itself. A full-rank lattice in dimension $n$ is stored as an $n \times n$ integer basis matrix whose columns are the basis vectors, and a lattice point is just the matrix-vector product $B x$ for some integer vector $x$:

import numpy as np

# The basis B_1 from the start of the chapter, columns are b_1 and b_2.
B1 = np.array([[3, 1], [1, 2]], dtype=np.int64)

def lattice_point(B, x):
    return tuple(int(a) for a in B @ np.asarray(x, dtype=np.int64))

# A handful of lattice points in L(B_1).
print(lattice_point(B1, [ 0,  0]))
# ==> (0, 0)
print(lattice_point(B1, [ 1,  1]))
# ==> (4, 3)
print(lattice_point(B1, [ 2, -1]))
# ==> (5, 0)
print(lattice_point(B1, [-1,  2]))
# ==> (-1, 3)

The change-of-basis check reduces to solving the integer linear system $B_2 = B_1 U$ and testing whether $U$ is unimodular:

import numpy as np

B1 = np.array([[3, 1], [1, 2]], dtype=np.int64)
B2 = np.array([[3, 4], [1, 3]], dtype=np.int64)

# Solve B_1 U = B_2 for U over the rationals; unimodular iff integer and det +/-1.
U = np.linalg.solve(B1.astype(float), B2.astype(float))
U_int = np.round(U).astype(np.int64)

print("U =", U_int.tolist())
# ==> U = [[1, 1], [0, 1]]
print("U is integer?", bool(np.allclose(U, U_int)))
# ==> U is integer? True
print("det U =", int(round(np.linalg.det(U_int.astype(float)))))
# ==> det U = 1

The determinant of the lattice is the absolute value of the determinant of any basis, and the equivalence theorem guarantees it is invariant under unimodular change of basis:

import numpy as np

B1 = np.array([[3, 1], [1, 2]], dtype=np.int64)
U  = np.array([[1, 1], [0, 1]], dtype=np.int64)
B2 = B1 @ U

det_B1 = abs(int(round(np.linalg.det(B1.astype(float)))))
det_B2 = abs(int(round(np.linalg.det(B2.astype(float)))))
print("|det B1| =", det_B1)
# ==> |det B1| = 5
print("|det B2| =", det_B2)
# ==> |det B2| = 5

The dual basis is $B^{-T}$, computed via numpy.linalg.inv and a transpose:

import numpy as np

B = np.array([[3, 1], [1, 2]], dtype=float)
D = np.linalg.inv(B).T

# The dual basis is rational; displaying 5 * D shows it as a small integer matrix.
print("5 * D =", np.round(5 * D).astype(np.int64).tolist())
# ==> 5 * D = [[2, -1], [-1, 3]]

# B^T @ D should equal I: every (dual, primal) pair has the right inner product.
identity = B.T @ D
print("B^T @ D rounded =", np.round(identity, 9).tolist())
# ==> B^T @ D rounded = [[1.0, 0.0], [0.0, 1.0]]

The dual-of-dual identity $(B^{-T})^{-T} = B$ is worth seeing explicitly:

import numpy as np

B = np.array([[3, 1], [1, 2]], dtype=float)
D  = np.linalg.inv(B).T
DD = np.linalg.inv(D).T
print("dual-of-dual equals B?", bool(np.allclose(DD, B)))
# ==> dual-of-dual equals B? True

Finally, Minkowski’s bound for the running example is $\sqrt{2} \cdot 5^{1/2} \approx 3.16$. An exhaustive search over small integer coefficients finds an explicit lattice vector under the bound (in fact, well under it):

import math
import numpy as np

B = np.array([[3, 1], [1, 2]], dtype=np.int64)
n = B.shape[1]
det_L = abs(int(round(np.linalg.det(B.astype(float)))))
bound = math.sqrt(n) * (det_L ** (1.0 / n))
print("det(L) =", det_L)
# ==> det(L) = 5
print("Minkowski bound =", round(bound, 4))
# ==> Minkowski bound = 3.1623

best_len = float("inf")
best_coef = None
for i in range(-3, 4):
    for j in range(-3, 4):
        if (i, j) == (0, 0):
            continue
        v = B @ np.array([i, j], dtype=np.int64)
        length = float(np.linalg.norm(v))
        if length < best_len:
            best_len = length
            best_coef = (i, j)

v = B @ np.array(best_coef, dtype=np.int64)
print("shortest coefficients:", best_coef)
# ==> shortest coefficients: (-1, 1)
print("shortest vector:", tuple(int(x) for x in v))
# ==> shortest vector: (-2, 1)
print("length =", round(best_len, 4))
# ==> length = 2.2361

The shortest vector has length $\sqrt{5} \approx 2.236$, safely below the Minkowski bound of $\sqrt{10} \approx 3.162$. The chapter’s pytest suite at tests/ch07/ runs the same checks on larger 2D and 3D examples and confirms the bound holds on every one of them.

SVP, CVP, and what the attacks look like

The two algorithmic problems Part II cares about are stated directly in terms of the successive minima. The first asks for a shortest vector, and the second asks for a lattice vector closest to a target point.

Shortest vector problem (SVP). The input is a basis $B$ of a full-rank lattice $L \subset \mathbb{R}^n$. The output is a nonzero vector $v \in L$ with $\|v\|_2 = \lambda_1(L)$ (Micciancio & Goldwasser, 2002).

Closest vector problem (CVP). The input is a basis $B$ of a full-rank lattice $L \subset \mathbb{R}^n$ together with a target point $t \in \mathbb{R}^n$. The output is a vector $v \in L$ minimizing $\|v - t\|_2$ (Micciancio & Goldwasser, 2002).

Both problems have approximate and gap variants. Fix a slack factor $\gamma \geq 1$.

• The approximate shortest vector problem $\mathrm{SVP}_\gamma$ asks for a nonzero $v \in L$ with $\|v\|_2 \leq \gamma \lambda_1(L)$ (Micciancio & Goldwasser, 2002).
• The gap shortest vector problem $\mathrm{GapSVP}_\gamma$ is the promise decision problem: given $B$ and a threshold $d$, decide whether $\lambda_1(L) \leq d$ or $\lambda_1(L) > \gamma d$, promised one case holds (Micciancio & Goldwasser, 2002).
• The approximate closest vector problem $\mathrm{CVP}_\gamma$ asks for $v \in L$ with $\|v - t\|_2 \leq \gamma \cdot \mathrm{dist}(t, L)$.
• The gap closest vector problem $\mathrm{GapCVP}_\gamma$ is the corresponding promise decision problem: decide whether $\mathrm{dist}(t, L) \leq d$ or $\mathrm{dist}(t, L) > \gamma d$.
• The shortest independent vectors problem $\mathrm{SIVP}_\gamma$ asks for $n$ linearly independent lattice vectors of maximum norm at most $\gamma \cdot \lambda_n(L)$ (Micciancio & Regev, 2009, sec. 2).

These approximate and gap problems are the language used in worst-case-to-average-case reductions. Regev’s 2009 result says, roughly, that efficient algorithms for suitable LWE instances would yield quantum algorithms for worst-case lattice problems such as $\mathrm{GapSVP}$ and $\mathrm{SIVP}$, at an approximation factor of $\tilde{O}(n/\alpha)$, which grows with the dimension $n$ and with the reciprocal of the LWE noise rate $\alpha$. The exact statement depends on the modulus and error rate. Chapter 8 states the parameterized version rather than treating $\gamma$ as an unspecified constant (Regev, 2009).

Minkowski’s bound is an upper bound on $\lambda_1$, which is the output norm of SVP. The bound shows that a short vector exists; it does not show how to find one. Closing the gap between “a short vector exists by Minkowski” and “here is an algorithm that produces one” is what lattice cryptanalysis is about. If an efficient algorithm closed that gap for the approximation factors and structured instances used in deployed schemes, the standard hardness assumptions behind Part II would be seriously undermined. Chapter 13 walks BKZ and its derivatives, explains how concrete attack estimates depend on a block-size parameter, and shows how ML-KEM’s parameters are evaluated against those estimates (Albrecht et al., 2024; Avanzi et al., 2021; National Institute of Standards and Technology, 2024).

One observation closes the section. SVP in dimension two is easy. A handful of integer combinations of the basis vectors can be checked by brute force, and a two-dimensional reduction algorithm (Lagrange’s method, a predecessor of the Lenstra-Lenstra-Lovász (LLL) algorithm) finds the shortest vector in polynomial time. ML-KEM-512 fixes a degree-$n$ polynomial ring with $n = 256$ and a module of rank $k = 2$, giving $k \cdot n = 512$ coefficients over $\mathbb{Z}_q$ with $q = 3329$ (National Institute of Standards and Technology, 2024). The concrete attacks are not simply “SVP in dimension 512”. They reduce the Module-LWE instance to $q$-ary lattice problems whose attack dimensions and costs depend on the chosen primal, dual, or hybrid attack model. Chapter 13 explains how BKZ-style estimates turn those structured Module-LWE instances into concrete security estimates.

Tradeoffs inside Part II

Lattices, bases, determinants, and dual lattices are the ambient objects every subsequent Part II chapter rests on.

Chapter	What it adds to the objects built here
8	Learning with errors (LWE), a computational assumption tied to $q$-ary lattices
9	Ring-LWE and Module-LWE: from plain integer lattices to structured modules
10	Regev encryption, the cleanest lattice public-key encryption scheme
11	ML-KEM, from Module-LWE plus the Fujisaki-Okamoto transform of Chapter 5
12	ML-DSA, which adds Module-SIS to Module-LWE and signs by Fiat-Shamir with aborts
13	Lattice cryptanalysis: BKZ, reduction, and the estimates that set ML-KEM’s parameters

Two of those rows are easy to misread. Read LWE as noisy linear algebra modulo $q$. Geometrically, a batch of LWE samples is a bounded-distance-decoding or noisy-CVP-style instance: the observed vector sits close to a structured $q$-ary lattice point, and the adversary must either recover the secret (search LWE) or tell the noisy samples from uniform (decisional LWE) (Regev, 2009). The ring $R_q = \mathbb{Z}_q[x]/(x^n + 1)$ that Chapter 9 works over is not itself a lattice; it is the modular arithmetic layer used to describe Ring-LWE and Module-LWE instances whose underlying hardness is analyzed through structured $q$-ary lattices.

The dual lattice earns its keep once the original lattice acquires ring structure. In the Ring-LWE and Module-LWE setting, the dual-lattice story is usually formulated before reduction modulo $q$, in the number-field and ring-of-integers setting: there the dual of the ring of integers is a fractional ideal related to the inverse different. Chapter 9 picks that up where it states the Ring-LWE hardness reduction, whose Gaussian widths and dual ideals are stated in the canonical embedding rather than in the coefficient representation concrete schemes compute with modulo $q$. The general definition from the algebra section above is what Chapter 9 draws on.

Chapter 8 is the immediate next step: it turns the objects built here into the LWE hardness assumption.

Exercises

Exercise 1. Verify a unimodular change of basis. Take $B_1$ and $B_2$ from the start of the chapter. Compute $U = B_1^{-1} B_2$ by hand, check that every entry is an integer, and compute $\det U$. Then construct $U$ a second way: express each column of $B_2$ as an integer combination of the columns of $B_1$ directly, and collect the coefficients into a matrix. The two constructions must agree.

Exercise 2. Dual-of-dual on a 3D lattice. Fix the basis

$$B = \begin{pmatrix} 2 & 0 & 1 \\ 1 & 3 & 0 \\ 0 & 1 & 4 \end{pmatrix}.$$

Compute the dual basis $D = B^{-T}$ in Python using numpy.linalg.inv and a transpose. Compute the dual of $D$ in the same way, call it $D^{(2)}$, and verify that $D^{(2)}$ equals $B$ up to floating-point error. Explain in one sentence why the entries of $D$ are in general rational rather than integer.

Exercise 3. Minkowski’s bound on a diagonal lattice. Take $B = \mathrm{diag}(2, 3, 5, 7)$ as a basis of a full-rank lattice $L \subset \mathbb{Z}^4$. Compute $\det(L)$ and Minkowski’s bound $\sqrt{4} \cdot \det(L)^{1/4}$ in Python. Then find an explicit nonzero lattice vector whose Euclidean norm is below the bound, and report its integer coefficients in the given basis.

Exercise 4. State SVP and CVP from memory. Without looking at the section above, write the shortest vector problem and the closest vector problem with their inputs and outputs. Then state the approximate versions $\mathrm{SVP}_\gamma$ and $\mathrm{CVP}_\gamma$, and the promise-decision versions $\mathrm{GapSVP}_\gamma$ and $\mathrm{GapCVP}_\gamma$. Check your statements against the definitions in Micciancio-Goldwasser 2002 (Micciancio & Goldwasser, 2002) and Regev 2009 (Regev, 2009), and note any differences.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 7. A separate track, for rebuilding rather than reading: the package exercises/ch07-lattices has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch07 to grade your version against the suite that proves the reference one.

References

Albrecht, M. R., et al. (2024). Lattice Estimator. Open-source tool, github.com/malb/lattice-estimator. https://github.com/malb/lattice-estimator

Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., & Stehlé, D. (2021). CRYSTALS-Kyber Algorithm Specifications and Supporting Documentation (Version 3.02). NIST Post-Quantum Cryptography Project, Round 3 submission package. https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf

Micciancio, D., & Goldwasser, S. (2002). Complexity of Lattice Problems: A Cryptographic Perspective (Vol. 671). Kluwer Academic Publishers. https://link.springer.com/book/10.1007/978-1-4615-0897-7

Micciancio, D., & Regev, O. (2009). Lattice-based cryptography. In D. J. Bernstein, J. Buchmann, & E. Dahmen (Eds.), Post-Quantum Cryptography (pp. 147–191). Springer. https://doi.org/10.1007/978-3-540-88702-7_5

National Institute of Standards and Technology. (2024). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.203

Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6), 34:1-34:40. https://doi.org/10.1145/1568318.1568324