Dave Ishii - Problem Solving Blog

Let's validate your approach to solving the Shortest Vector Problem (SVP) for the given 2D lattice.

Your method is a brute-force enumeration, and I'll break down its validity, its limitations, and how it relates to standard algorithms.

Your Method Summarized

First, let's formalize what you're doing.

• Lattice Basis: You are given two basis vectors that define the lattice:

• Goal: The goal is to find a non-zero lattice vector , where and are integers, such that its length (Euclidean norm) is minimized.

• Your Algorithm: You are systematically checking all possible integer combinations of and within an expanding search radius.

  • Round 1: Test all .

  • Round 2: Test all .

  • Round 3: Test all , and so on.

---

Validation ✅

Your approach is conceptually correct. It is guaranteed to eventually find the shortest non-zero vector in the lattice.

By definition, every vector in the lattice can be expressed as an integer linear combination of the basis vectors. The shortest vector must have some integer coefficients . As you increase the search bounds of your "rounds," you will eventually test those specific coefficients and find the shortest vector.

In your example, you correctly identified that the vectors and are the shortest vectors found in your first two rounds.

• Length:

This is indeed the correct shortest non-zero vector for this lattice.

---

Limitations & Analysis ❌

While your method works for this small 2D example, it has a critical flaw that makes it unusable for most practical purposes: it is extremely inefficient.

1. The Curse of Dimensionality

The core problem is its complexity. In each "round" , you test all coefficients in the range .

• For a 2D lattice, the number of vectors to check is .

• For an -dimensional lattice, this becomes .

The number of combinations grows exponentially with the dimension .

• Your 2D Case (Round 2, k=2): You checked vectors. This is trivial for a computer.

• A 30D Case (Round 1, k=1): You would need to check (200 trillion) vectors. This is computationally infeasible.

Lattices used in cryptography can have hundreds of dimensions, making this brute-force approach impossible.

2. No Stopping Guarantee

You don't know when to stop. How many rounds do you need to run to be sure you have the shortest vector? The coefficients for the shortest vector might be very large. Stopping after "Round 3" gives you the shortest vector found so far, but provides no guarantee that it's the true shortest vector of the entire lattice.

---

How SVP is Solved in Practice

Your method is a basic version of enumeration. Modern algorithms are much more sophisticated.

1. Lattice Basis Reduction (e.g., LLL Algorithm): Before searching, the first step is almost always to "reduce" the basis. Algorithms like LLL (Lenstra–Lenstra–Lovász) find a new basis for the same lattice whose vectors are shorter and more orthogonal. The first vector of an LLL-reduced basis is often a very good approximation of the shortest vector. This is a polynomial-time algorithm and is fundamental to lattice cryptography.

2. Smarter Enumeration (e.g., Kannan, Fincke-Pohst): These algorithms don't search a simple cube of coefficients. They use the geometric structure of the lattice (specifically, the Gram-Schmidt orthogonalization) to intelligently prune the search space. They can prove that certain branches of the search tree cannot possibly contain a shorter vector, allowing them to skip checking billions of combinations.

3. Sieving Algorithms: For high dimensions, sieving algorithms are the state-of-the-art for solving exact SVP. They work by generating a large list of lattice vectors and repeatedly combining them to find shorter and shorter ones.

Conclusion

Your approach is an excellent way to understand the fundamental definition of SVP. It is correct in principle and works for tiny examples.

However, its exponential complexity makes it completely impractical for the high-dimensional lattices used in modern applications like cryptography. It's like trying to find the lowest point on Earth by checking the elevation of every single square meter—you'll get there eventually, but there are far more intelligent ways to search.

(CVP)