Solving Lattice SVP and CVP Problems: A Step-by-Step Guide
Introduction
Lattice problems are fundamental to cryptography and computational mathematics. In this post, I'll walk through solving Shortest Vector Problem (SVP) and Closest Vector Problem (CVP) instances, showing the reasoning behind each step.
Understanding the Basics
Lattice vectors are integer linear combinations of basis vectors:
- v = c₁b₁ + c₂b₂ + ... where all cᵢ are integers
SVP Goal: Find the shortest non-zero vector in the lattice
CVP Goal: Find the lattice vector closest to a given target point
SVP Solutions
Problem 1: (3,1) and (1,3) - The Simple Case
Strategy: Start with small integer coefficients (0, ±1, ±2)
Testing combinations:
- b₁ = (3,1), norm² = 10
- b₂ = (1,3), norm² = 10
- b₁ + b₂ = (4,4), norm² = 32
- b₁ - b₂ = (2,-2), norm² = 8 ✓
- 2b₁ = (6,2), norm² = 40
- 2b₂ = (2,6), norm² = 40
Answer: (2,-2) from b₁ - b₂, norm = 2√2
Key insight: The difference of similar-magnitude vectors often yields shorter results.
Problem 2: (5,2) and (2,5) - Same Pattern
This follows the same structure as Problem 1.
Testing:
- b₁ = (5,2), norm² = 29
- b₂ = (2,5), norm² = 29
- b₁ - b₂ = (3,-3), norm² = 18 ✓
Answer: (3,-3) from b₁ - b₂, norm = 3√2
Problem 3: (2,0,0), (1,2,0), (1,1,2) - Lower Triangular
Strategy: In lower triangular bases, the first basis vector is often shortest.
Testing:
- b₁ = (2,0,0), norm² = 4 ✓
- b₂ = (1,2,0), norm² = 5
- b₃ = (1,1,2), norm² = 6
- b₁ - b₂ = (1,-2,0), norm² = 5
- b₂ - b₃ = (0,1,-2), norm² = 5
Answer: (2,0,0) from b₁, norm = 2
Why this works: Lower triangular structure means b₁ aligns with an axis.
Problem 4: (7,3) and (5,8) - Finding Hidden Structure
This requires more systematic checking.
Key candidates:
- b₁ = (7,3), norm² = 58
- b₂ = (5,8), norm² = 89
- b₁ - b₂ = (2,-5), norm² = 29 ✓
- b₁ - 2b₂ = (-3,-13), norm² = 178
- 2b₁ - b₂ = (9,-2), norm² = 85
Answer: (2,-5) from b₁ - b₂, norm ≈ 5.39
Problem 5: (4,1,0), (1,4,1), (0,1,4) - Circular Symmetry
Strategy: Notice the cyclic pattern in the basis vectors.
Testing basis vectors:
- b₁ = (4,1,0), norm² = 17 ✓
- b₂ = (1,4,1), norm² = 18
- b₃ = (0,1,4), norm² = 17 ✓
Testing differences:
- b₁ - b₂ = (3,-3,-1), norm² = 19
- b₂ - b₃ = (1,3,-3), norm² = 19
Answer: (4,1,0) or (0,1,4), norm ≈ 4.12
Note: Multiple shortest vectors exist due to symmetry!
CVP Solutions
Problem 1: Target (5,7) with Orthogonal Basis (3,0), (0,3)
Strategy: With an orthogonal basis, use Babai's rounding algorithm.
Step 1: Express target in basis coordinates
- t = (5,7) = (5/3)b₁ + (7/3)b₂ = 1.67b₁ + 2.33b₂
Step 2: Round coefficients
- c₁ = round(1.67) = 2
- c₂ = round(2.33) = 2
Step 3: Compute closest vector
- v = 2b₁ + 2b₂ = (6,6)
Answer: (6,6), distance = √2
Problem 2: Target (6,8) with (4,1), (1,4)
Step 1: Express target in basis (solve 4c₁ + c₂ = 6, c₁ + 4c₂ = 8)
- From first equation: c₂ = 6 - 4c₁
- Substitute: c₁ + 4(6 - 4c₁) = 8
- c₁ + 24 - 16c₁ = 8
- -15c₁ = -16, so c₁ ≈ 1.07
- c₂ ≈ 1.73
Step 2: Test rounded values
- (1,2): v = b₁ + 2b₂ = (6,9), distance = 1 ✓
- (1,1): v = (5,5), distance ≈ 3.16
- (2,2): v = (10,10), distance ≈ 2.83
Answer: (6,9), distance = 1
Problem 3: Target (7.5,9.3) with (5,2), (2,5)
Step 1: Solve for approximate coefficients
- 5c₁ + 2c₂ = 7.5
- 2c₁ + 5c₂ = 9.3
- Solution: c₁ ≈ 0.86, c₂ ≈ 1.57
Step 2: Test nearby integer combinations
- (1,2): v = (9,12), distance ≈ 3.35
- (1,1): v = (7,7), distance ≈ 2.35 ✓
- (0,2): v = (4,10), distance ≈ 3.57
- (2,1): v = (12,9), distance ≈ 4.52
Answer: (7,7), distance ≈ 2.35
Problem 4: Target (3,5,7) with Diagonal Basis (2,0,0), (0,2,0), (0,0,2)
Strategy: Orthogonal basis makes this straightforward.
Step 1: Divide each coordinate by 2
- c₁ = 3/2 = 1.5 → round to 2
- c₂ = 5/2 = 2.5 → can round to 2 or 3
- c₃ = 7/2 = 3.5 → round to 4
Step 2: Check both options for c₂
- (2,2,4): v = (4,4,8), distance² = 1+1+1 = 3 ✓
- (2,3,4): v = (4,6,8), distance² = 1+1+1 = 3 ✓
Answer: (4,4,8) or (4,6,8), distance = √3
Problem 5: Target (5,6,4) with (3,1,0), (1,3,1), (0,1,3)
Step 1: Solve the system
- 3c₁ + c₂ = 5
- c₁ + 3c₂ + c₃ = 6
- c₂ + 3c₃ = 4
From equations: c₁ ≈ 1.27, c₂ ≈ 1.18, c₃ ≈ 0.94
Step 2: Test (1,1,1)
- v = (3,1,0) + (1,3,1) + (0,1,3) = (4,5,4)
- Distance² = (5-4)² + (6-5)² + (4-4)² = 2 ✓
Step 3: Verify neighbors
- (1,2,1): v = (4,8,5), distance² = 6
- (2,1,1): v = (7,6,4), distance² = 4
Answer: (4,5,4), distance = √2
Problem 6: Target (10,10) with (6,2), (3,7) - The Tricky One
Why it's tricky: Non-orthogonal basis with similar-length vectors at an angle.
Step 1: Solve for coefficients
- 6c₁ + 3c₂ = 10
- 2c₁ + 7c₂ = 10
- Solution: c₁ ≈ 1.25, c₂ ≈ 0.83
Step 2: Test nearby combinations
- (1,1): v = (9,9), distance² = 2 ✓
- (1,2): v = (12,16), distance² = 40
- (2,0): v = (12,4), distance² = 40
- (2,1): v = (15,11), distance² = 26
Answer: (9,9), distance = √2
Key insight: Even when Babai's rounding suggests (1,1), we must verify!
General Strategies
For SVP:
- Always test the basis vectors themselves
- Try differences and sums of basis vectors
- Check small multiples (2b₁, 2b₂)
- Look for structural patterns (symmetry, triangular form)
- Systematically expand to larger coefficients if needed
For CVP:
- Use Babai's algorithm (round basis representation) as starting point
- Always verify neighbors (±1 in each coefficient)
- With orthogonal bases, rounding is usually optimal
- With non-orthogonal bases, check more carefully
- Calculate distances explicitly to confirm
Computational Tip: For norm comparison, use squared norms to avoid square roots until the final answer.
Conclusion
These problems demonstrate that even small lattice instances require careful checking. The key is systematic exploration combined with geometric intuition about how lattice vectors relate to each other. In higher dimensions or with larger coefficients, these problems become computationally hard—which is why they're used in cryptography!
Happy lattice problem solving! 🔢