08b-shortest-vector-problem.ipynb

Kernel: SageMath 10.5

The Shortest Vector Problem

Module 08 | 08-lattices-post-quantum

SVP definition, good vs bad bases, successive minima, Minkowski bounds, brute-force enumeration

Objectives

By the end of this notebook you will be able to:

1. Define the Shortest Vector Problem (SVP) and its approximate variant $\gamma$-SVP.

2. Explain why SVP is easy with a good basis but computationally hard in general.

3. Compute successive minima $\lambda_1, \lambda_2$ for small lattices.

4. Apply Minkowski's theorem and the Gaussian heuristic to estimate shortest vector lengths.

5. Connect SVP hardness to the security of post-quantum cryptosystems like Kyber and Dilithium.

Prerequisites

• Completion of Lattices and Bases (08a) — you should be comfortable with lattice bases, integer linear combinations, and the idea that different bases can generate the same lattice.

• Basic linear algebra: norms, determinants, Gram-Schmidt orthogonalization.

From Bases to Hard Problems

Bridge from 08a: In the previous notebook, we saw that a lattice can have many different bases. Some bases are "good" — short, nearly orthogonal vectors — and some are "bad" — long, nearly parallel vectors. We even saw that a unimodular transformation $U$ can turn a nice basis into a terrible one while keeping the lattice unchanged.

This raises a natural question: if I hand you a bad basis, can you find a short lattice vector? This is essentially the Shortest Vector Problem, and it turns out to be one of the hardest problems in computational mathematics.

Motivating Question: I give you a lattice basis in 500 dimensions. Somewhere in that lattice is a vector of length 1. Can you find it? The best known algorithms would take roughly $2^{250}$ operations — far more than the number of atoms in the observable universe. This hardness is exactly what makes post-quantum cryptography possible.

1. SVP: The Definition

The Shortest Vector Problem (SVP): Given a basis $B = \{\mathbf{b}_1, \ldots, \mathbf{b}_n\}$ of a lattice $L$, find a nonzero vector $\mathbf{v} \in L$ such that

$$\|\mathbf{v}\| \leq \|\mathbf{w}\| \quad \text{for all nonzero } \mathbf{w} \in L.$$

We write $\lambda_1(L) = \|\mathbf{v}\|$ for the length of this shortest nonzero vector (using the Euclidean norm).

The key subtlety: the problem gives you a basis, not the lattice itself. The lattice is infinite, and you only see it through the window of whatever basis you are given. A good basis makes $\lambda_1$ obvious; a bad basis hides it completely.

2. SVP Is Easy with a Good Basis

If the basis vectors are orthogonal (or nearly so), the shortest lattice vector is simply the shortest basis vector. Let us verify this.

# A "good" (orthogonal) basis: the shortest vector is obvious
B_good = matrix(ZZ, [[3, 0],
                      [0, 5]])

print("Basis vectors:")
print(f"  b1 = {B_good[0]},  ||b1|| = {B_good[0].norm().n(digits=4)}")
print(f"  b2 = {B_good[1]},  ||b2|| = {B_good[1].norm().n(digits=4)}")
print(f"\nShortest basis vector: b1 with length {B_good[0].norm().n(digits=4)}")
print("When the basis is orthogonal, the shortest basis vector IS the shortest lattice vector.")
print(f"So lambda_1 = {B_good[0].norm().n(digits=4)}")

3. SVP Is Hard with a Bad Basis

Now let us take the same lattice but present it with a "bad" basis — one where the vectors are long and nearly parallel. Can you spot the shortest vector just by looking at the basis?

Checkpoint: Before running the next cell, look at the bad basis vectors below. Can you guess what $\lambda_1$ is? (Hint: it is the same lattice as above!)

# Apply a unimodular transformation to get a "bad" basis for the SAME lattice
U = matrix(ZZ, [[7, 3],
                 [2, 1]])  # det(U) = 7*1 - 3*2 = 1, so unimodular
B_bad = U * B_good

print("Bad basis vectors:")
print(f"  b1' = {B_bad[0]},  ||b1'|| = {B_bad[0].norm().n(digits=4)}")
print(f"  b2' = {B_bad[1]},  ||b2'|| = {B_bad[1].norm().n(digits=4)}")
print(f"\nBoth basis vectors have length > {min(B_bad[0].norm(), B_bad[1].norm()).n(digits=4)}")
print(f"But we KNOW lambda_1 = 3 (the vector (3, 0) is still in the lattice!)")
print(f"\nThe bad basis completely hides the short vector.")

# Visualize: same lattice, two bases, the short vector is hidden by the bad basis

def plot_lattice_2d(B, bound=20, point_color='blue', point_size=30):
    """Plot lattice points generated by 2D basis B within a bounding box."""
    pts = []
    for i in range(-bound, bound+1):
        for j in range(-bound, bound+1):
            v = i * B[0] + j * B[1]
            if abs(v[0]) <= 25 and abs(v[1]) <= 25:
                pts.append(v)
    P = points(pts, color=point_color, size=point_size, zorder=5)
    return P

# Plot lattice points
lattice_plot = plot_lattice_2d(B_good)

# Overlay bad basis vectors (red arrows)
bad_arrows = arrow((0,0), B_bad[0], color='red', width=2, zorder=10)
bad_arrows += arrow((0,0), B_bad[1], color='red', width=2, zorder=10)

# Overlay good basis vectors (green arrows)
good_arrows = arrow((0,0), B_good[0], color='green', width=2, linestyle='dashed', zorder=10)
good_arrows += arrow((0,0), B_good[1], color='green', width=2, linestyle='dashed', zorder=10)

# Highlight the shortest vector
sv = arrow((0,0), (3, 0), color='gold', width=3, zorder=15)
sv_label = text("shortest!", (3, -1.5), fontsize=12, color='goldenrod')

show(lattice_plot + bad_arrows + good_arrows + sv + sv_label,
     axes=True, aspect_ratio=1, figsize=8,
     title="Same lattice: green = good basis, red = bad basis, gold = shortest vector")

Misconception Alert: "SVP is easy — just try all lattice vectors!"

This is tempting but fatally flawed. The number of lattice points within a ball of radius $r$ grows as roughly $r^n$ in dimension $n$. In dimension $n = 500$, even restricting to vectors of length $\leq 100$ gives on the order of $100^{500} = 10^{1000}$ candidates. No computer can enumerate this. SVP is easy in 2D (we can draw the picture!) but becomes astronomically hard as the dimension grows.

4. Successive Minima

The shortest vector length $\lambda_1$ is just the first of a sequence of important quantities.

Definition (Successive Minima). For an $n$-dimensional lattice $L$, the $i$-th successive minimum $\lambda_i(L)$ is the smallest radius $r$ such that the ball of radius $r$ centered at the origin contains $i$ linearly independent lattice vectors:

$$\lambda_i(L) = \inf\{r : \dim(\text{span}(L \cap \bar{B}(0, r))) \geq i\}$$

In particular:

• $\lambda_1(L)$ = length of the shortest nonzero lattice vector

• $\lambda_2(L)$ = length of the shortest vector linearly independent from the $\lambda_1$-vector

Let us compute these for a concrete lattice.

# Compute successive minima by brute-force enumeration in 2D
B = matrix(ZZ, [[4, 1],
                 [1, 3]])

print(f"Basis:\n{B}")
print(f"Lattice determinant: det(B) = {det(B)}")

# Enumerate lattice points and find shortest vectors
candidates = []
search_range = 15
for i in range(-search_range, search_range + 1):
    for j in range(-search_range, search_range + 1):
        if i == 0 and j == 0:
            continue
        v = i * B[0] + j * B[1]
        candidates.append((v.norm().n(), v, (i, j)))

candidates.sort(key=lambda x: x[0])

# lambda_1: shortest vector
lam1_norm, lam1_vec, lam1_coeffs = candidates[0]
print(f"\nlambda_1 = {lam1_norm:.4f}")
print(f"  Achieved by: {lam1_vec} = {lam1_coeffs[0]}*b1 + {lam1_coeffs[1]}*b2")

# lambda_2: shortest vector linearly independent from lambda_1 vector
for norm_val, vec, coeffs in candidates:
    # Check linear independence with lam1_vec
    M = matrix([lam1_vec, vec])
    if M.rank() == 2:
        lam2_norm, lam2_vec, lam2_coeffs = norm_val, vec, coeffs
        break

print(f"\nlambda_2 = {lam2_norm:.4f}")
print(f"  Achieved by: {lam2_vec} = {lam2_coeffs[0]}*b1 + {lam2_coeffs[1]}*b2")

5. Approximate SVP: the $\gamma$-SVP Problem

Exact SVP is NP-hard (under randomized reductions). But even approximate SVP is believed to be hard!

$\gamma$-SVP: Given a basis $B$ of lattice $L$, find a nonzero vector $\mathbf{v} \in L$ with

$$\|\mathbf{v}\| \leq \gamma \cdot \lambda_1(L).$$

The factor $\gamma \geq 1$ is the approximation factor:

• $\gamma = 1$: exact SVP (hardest)

• $\gamma = 2^{n/2}$: what LLL achieves (polynomial time, but exponential approximation factor)

• $\gamma = \text{poly}(n)$: believed to be hard! This is the regime that cryptography relies on.

Crypto Foreshadowing: The LLL algorithm (next notebook, 08c) approximately solves SVP with $\gamma = 2^{n/2}$. This is good enough to break some old cryptosystems (knapsack-based schemes, for instance), but not good enough to break Kyber or Dilithium, which require $\gamma = \text{poly}(n)$ approximation.

6. How Short Can the Shortest Vector Be?

We need bounds on $\lambda_1$ to understand what "short" means for a given lattice.

Minkowski's Theorem

Theorem (Minkowski, 1896). For any $n$-dimensional lattice $L$,

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

More precisely, $\lambda_1(L) \leq \sqrt{\gamma_n} \cdot \det(L)^{1/n}$ where $\gamma_n$ is Hermite's constant — the smallest value such that the bound holds for every $n$-dimensional lattice.

Known values of $\gamma_n$: $\gamma_1 = 1$, $\gamma_2 = \tfrac{2}{\sqrt{3}}$, $\gamma_3 = 2^{1/3}$, $\gamma_4 = \sqrt{2}$, ...

For large $n$: $\gamma_n \approx \frac{n}{2\pi e}$ (asymptotically).

The Gaussian Heuristic

For a "random" lattice in dimension $n$, the expected shortest vector length is approximately:

$$\lambda_1(L) \approx \sqrt{\frac{n}{2\pi e}} \cdot \det(L)^{1/n}$$

This is the Gaussian heuristic. It tells us that in high dimensions, the shortest vector length grows like $\sqrt{n}$ times the $n$-th root of the determinant.

# Compare Minkowski bound, Gaussian heuristic, and actual lambda_1

B = matrix(ZZ, [[4, 1],
                 [1, 3]])
n = B.nrows()
det_L = abs(det(B))

# Minkowski bound: lambda_1 <= sqrt(n) * det(L)^(1/n)
minkowski_bound = sqrt(n) * det_L^(1/n)

# Gaussian heuristic: lambda_1 ~ sqrt(n / (2*pi*e)) * det(L)^(1/n)
gaussian_heuristic = sqrt(n / (2 * pi * e)) * det_L^(1/n)

# Actual lambda_1 (from our earlier brute-force computation)
actual_lambda1 = lam1_norm

print(f"Lattice dimension: n = {n}")
print(f"Lattice determinant: det(L) = {det_L}")
print(f"")
print(f"Minkowski bound:    lambda_1 <= {minkowski_bound:.4f}")
print(f"Gaussian heuristic: lambda_1 ~  {gaussian_heuristic:.4f}")
print(f"Actual lambda_1:    lambda_1 =  {actual_lambda1:.4f}")
print(f"")
print("In 2D the bounds are loose. They become tight in high dimensions.")

# How the Gaussian heuristic scales with dimension
# For a "unit determinant" lattice (det = 1), the expected shortest vector grows as sqrt(n/(2*pi*e))

dims = list(range(2, 502, 10))
gh_values = [sqrt(d / (2 * pi * e)) for d in dims]

P = list_plot(list(zip(dims, gh_values)), plotjoined=True, color='blue', thickness=2)
P += text("Gaussian heuristic: sqrt(n/(2*pi*e))", (300, 4), fontsize=11, color='blue')

show(P, axes_labels=['dimension $n$', '$\\lambda_1$ (det=1)'], figsize=(8, 4),
     title="Expected shortest vector length vs. dimension (det(L)=1)")

7. Brute-Force SVP in 2D

In low dimensions we can solve SVP exactly by enumerating all lattice points within a radius bound and keeping the shortest. Let us implement this and see why it is completely infeasible in high dimensions.

Checkpoint: Before running the next cell, think about this: if we search all integer combinations $a_1 \mathbf{b}_1 + a_2 \mathbf{b}_2$ with $|a_i| \leq k$, how many vectors do we check? How does this grow in dimension $n$?

def brute_force_svp(B, search_bound=20):
    """
    Solve SVP by exhaustive enumeration.
    Only feasible for small dimensions and small search_bound.
    """
    n = B.nrows()
    best_norm = Infinity
    best_vec = None
    count = 0
    
    # Generate all coefficient tuples in [-search_bound, search_bound]^n
    from itertools import product
    for coeffs in product(range(-search_bound, search_bound + 1), repeat=n):
        if all(c == 0 for c in coeffs):
            continue
        count += 1
        v = sum(c * B[i] for i, c in enumerate(coeffs))
        v_norm = v.norm()
        if v_norm < best_norm:
            best_norm = v_norm
            best_vec = v
    
    return best_vec, best_norm.n(digits=6), count

# Test on our 2D lattice with the BAD basis
B_bad_test = matrix(ZZ, [[21, 15],
                          [6,  5]])
print(f"Bad basis:\n{B_bad_test}")
print(f"Basis vector norms: {B_bad_test[0].norm().n(digits=4)}, {B_bad_test[1].norm().n(digits=4)}")
print()

sv, sv_norm, num_checked = brute_force_svp(B_bad_test, search_bound=30)
print(f"Shortest vector: {sv}")
print(f"Length: {sv_norm}")
print(f"Vectors checked: {num_checked}")
print()
print("Now imagine doing this in dimension 500...")

# The enumeration explosion: vectors checked grows as (2k+1)^n - 1

k = 10  # search bound
print(f"Search bound k = {k}: checking (2*{k}+1)^n - 1 vectors\n")
print("Dimension n Vectors to check Feasible?")
for n in [2, 3, 5, 10, 20, 50, 100, 500]:
    count = (2*k + 1)^n - 1
    if count < 10^9:
        feasible = "Yes"
    elif count < 10^15:
        feasible = "Barely"
    else:
        feasible = "NO"
    # Use scientific notation for large numbers
    if count < 10^12:
        print(f"{n} {count:>20,} {feasible}")
    else:
        print(f"{n} {'~' + f'10^{RR(log(count, 10)).n(digits=3)}':>20} {feasible}")

print("\nThis is why brute-force SVP is only possible in very low dimensions.")

8. Connection to Cryptography

The hardness of SVP (and its approximate variant) is the foundation of lattice-based cryptography.

Here is the key chain of ideas:

1. SVP is hard in high dimensions. No known algorithm solves exact SVP in polynomial time. The best algorithms (lattice sieving) run in time $2^{\Theta(n)}$.

2. Approximate SVP is also hard. For polynomial approximation factors $\gamma = \text{poly}(n)$, no efficient algorithm is known. Even quantum computers do not help!

3. LWE reduces to approximate SVP. The Learning With Errors problem (notebook 08d) has a worst-case to average-case reduction: if you can solve random LWE instances, you can solve approximate SVP on any lattice.

4. Kyber and Dilithium are built on LWE/MLWE. These NIST post-quantum standards derive their security from the assumed hardness of structured variants of SVP.

Algorithm	Based on	Security relies on
Kyber (ML-KEM)	Module-LWE	Approximate SVP in module lattices
Dilithium (ML-DSA)	Module-LWE + SIS	Approximate SVP + Short Integer Solution

Crypto Foreshadowing: In the next notebook (08c), we will implement the LLL algorithm, which solves SVP with approximation factor $\gamma = 2^{n/2}$. This exponential factor is too large to threaten Kyber (which only needs $\gamma = \text{poly}(n)$ hardness), but it is enough to break some classical lattice schemes. The gap between what LLL achieves and what cryptography needs is precisely where security lives.

---

Exercises

Exercise 1: Finding $\lambda_1$ and $\lambda_2$ (Fully Worked)

Problem: For the lattice with basis $B = \begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix}$, find $\lambda_1(L)$ and $\lambda_2(L)$.

Solution: We enumerate lattice points and sort by norm.

# EXERCISE 1: Fully worked solution

B_ex1 = matrix(ZZ, [[2, 1],
                      [1, 3]])

print(f"Basis B:\n{B_ex1}")
print(f"det(B) = {det(B_ex1)}")
print()

# Step 1: Enumerate lattice points
candidates = []
for i in range(-20, 21):
    for j in range(-20, 21):
        if i == 0 and j == 0:
            continue
        v = i * B_ex1[0] + j * B_ex1[1]
        candidates.append((v.norm().n(), v))

candidates.sort(key=lambda x: x[0])

# Step 2: lambda_1 is the smallest norm
lam1 = candidates[0]
print(f"lambda_1 = {lam1[0]:.4f}, achieved by {lam1[1]}")

# Step 3: lambda_2 is the smallest norm among vectors linearly independent from lambda_1
for norm_val, vec in candidates:
    M = matrix([lam1[1], vec])
    if M.rank() == 2:
        print(f"lambda_2 = {norm_val:.4f}, achieved by {vec}")
        break

# Step 4: Visualize
pts = []
for i in range(-10, 11):
    for j in range(-10, 11):
        v = i * B_ex1[0] + j * B_ex1[1]
        if abs(v[0]) <= 12 and abs(v[1]) <= 12:
            pts.append(v)

P = points(pts, color='blue', size=25, zorder=5)
P += circle((0, 0), lam1[0], color='green', linestyle='dashed', thickness=2)
P += circle((0, 0), norm_val, color='orange', linestyle='dashed', thickness=2)
P += arrow((0,0), lam1[1], color='green', width=2, zorder=10)
P += arrow((0,0), vec, color='orange', width=2, zorder=10)
P += text(f"$\\lambda_1$ = {lam1[0]:.2f}", (lam1[1][0]+1, lam1[1][1]+1), color='green', fontsize=11)
P += text(f"$\\lambda_2$ = {norm_val:.2f}", (vec[0]+1, vec[1]+1), color='orange', fontsize=11)
show(P, axes=True, aspect_ratio=1, figsize=7,
     title="Exercise 1: lambda_1 (green) and lambda_2 (orange) with norm circles")

Exercise 2: Minkowski Bound Check (Guided)

Problem: For the lattice with basis $B = \begin{pmatrix} 7 & 2 \\ 3 & 5 \end{pmatrix}$:

1. Compute $\det(L)$.

2. Compute the Minkowski bound $\sqrt{n} \cdot \det(L)^{1/n}$.

3. Compute the Gaussian heuristic estimate.

4. Find the actual $\lambda_1$ using brute_force_svp (defined earlier).

5. Verify that $\lambda_1 \leq$ Minkowski bound.

Scaffolding: The structure is provided below. Fill in the lines marked # YOUR CODE.

# EXERCISE 2: Guided (fill in YOUR CODE lines)

B_ex2 = matrix(ZZ, [[7, 2],
                      [3, 5]])
n = 2

# Step 1: Compute determinant
det_L = abs(det(B_ex2))  # YOUR CODE: compute det
print(f"det(L) = {det_L}")

# Step 2: Minkowski bound
# YOUR CODE: mink_bound = ...
# print(f"Minkowski bound: {mink_bound:.4f}")

# Step 3: Gaussian heuristic
# YOUR CODE: gh = ...
# print(f"Gaussian heuristic: {gh:.4f}")

# Step 4: Actual lambda_1 (use brute_force_svp from earlier)
# YOUR CODE: sv, sv_norm, _ = brute_force_svp(B_ex2)
# print(f"Actual lambda_1 = {sv_norm}, vector = {sv}")

# Step 5: Verify
# YOUR CODE: assert float(sv_norm) <= float(mink_bound), "Minkowski violated!"
# print("Minkowski bound holds!")

Exercise 3: Bad Basis Challenge (Independent)

Problem: I give you this basis for a 2D lattice:

$$B = \begin{pmatrix} 1432 & 897 \\ 2311 & 1448 \end{pmatrix}$$

The basis vectors have norms around 1690 and 2727. But the shortest lattice vector is much shorter than either basis vector.

Your tasks:

1. Use brute_force_svp to find $\lambda_1$ and the shortest vector.

2. Compare the shortest vector length to the basis vector lengths. What is the ratio?

3. Use SageMath's built-in .LLL() method on the basis and examine the first row. Is it the shortest vector?

4. Reflect: Why is this problem trivial in 2D but terrifying in 500D?

# EXERCISE 3: Independent — solve the bad-basis challenge

B_ex3 = matrix(ZZ, [[1432, 897],
                      [2311, 1448]])

# Your code here!

---

Summary

Concept	Key idea
SVP definition	Given a lattice basis $B$, find the shortest nonzero vector in $L(B)$. Its length is $\lambda_1(L)$.
Basis quality matters	With a good (nearly orthogonal) basis, the shortest vector is a basis vector. With a bad basis, it is hidden and hard to find.
Successive minima	$\lambda_1, \lambda_2, \ldots$ capture the sequence of shortest linearly independent vectors in the lattice
Minkowski's theorem	Upper bound: $\lambda_1 \leq \sqrt{n} \cdot \det(L)^{1/n}$. The Gaussian heuristic predicts the typical value.
Brute-force enumeration	Works in 2D but is infeasible in high dimensions, where the search space grows as $(2k+1)^n$
Approximate SVP	$\gamma$-SVP is also believed hard for polynomial $\gamma$. This is the foundation of Kyber, Dilithium, and all lattice-based post-quantum crypto.

Next: The LLL Algorithm (08c) — a polynomial-time algorithm that approximately solves SVP with factor $\gamma = 2^{n/2}$.