Solving the Closest Vector Problem (CVP) with Python

The Closest Vector Problem (CVP) is a fundamental problem in lattice theory and cryptography. Given a lattice basis and a target point, the goal is to find the lattice point that is closest to the target.

Problem Definition

Let $\mathbf{B} = [\mathbf{b}_1, \mathbf{b}_2, …, \mathbf{b}_n]$ be a basis for a lattice $\mathcal{L}$. For a given target vector $\mathbf{t}$, the CVP asks us to find:

$$\mathbf{v}^* = \arg\min_{\mathbf{v} \in \mathcal{L}} |\mathbf{t} - \mathbf{v}|$$

where $\mathbf{v} = \mathbf{B}\mathbf{x}$ for some integer vector $\mathbf{x}$.

Example Problem

We’ll solve a 2D CVP instance where:

• Lattice basis: $\mathbf{B} = \begin{pmatrix} 3 & 1 \ 1 & 2 \end{pmatrix}$
• Target point: $\mathbf{t} = (5.7, 3.2)$

Complete Python Implementation

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from scipy.linalg import qr
import time

def babai_algorithm(basis, target):
    """
    Babai's nearest plane algorithm for CVP approximation
    
    Args:
        basis: numpy array of shape (n, n) representing lattice basis
        target: numpy array of shape (n,) representing target point
    
    Returns:
        closest_point: approximation of closest lattice point
        coefficients: integer coefficients
    """
    # Gram-Schmidt orthogonalization
    Q, R = qr(basis.T)
    
    # Solve for coefficients in the orthogonal basis
    coeffs_real = np.linalg.solve(basis.T, target)
    
    # Round to nearest integers (Babai's rounding)
    coeffs_int = np.round(coeffs_real).astype(int)
    
    # Compute the closest lattice point
    closest_point = basis.T @ coeffs_int
    
    return closest_point, coeffs_int

def enumerate_cvp(basis, target, search_radius=5):
    """
    Brute force enumeration to find exact CVP solution
    
    Args:
        basis: numpy array of shape (n, n)
        target: numpy array of shape (n,)
        search_radius: how far to search in coefficient space
    
    Returns:
        best_point: exact closest lattice point
        best_coeffs: corresponding coefficients
        min_distance: minimum distance found
    """
    n = basis.shape[1]
    best_distance = float('inf')
    best_point = None
    best_coeffs = None
    
    # Generate all integer combinations within search radius
    ranges = [range(-search_radius, search_radius + 1) for _ in range(n)]
    
    import itertools
    for coeffs in itertools.product(*ranges):
        coeffs_array = np.array(coeffs)
        lattice_point = basis.T @ coeffs_array
        distance = np.linalg.norm(target - lattice_point)
        
        if distance < best_distance:
            best_distance = distance
            best_point = lattice_point
            best_coeffs = coeffs_array
    
    return best_point, best_coeffs, best_distance

def generate_lattice_points(basis, range_limit=5):
    """
    Generate lattice points for visualization
    """
    n = basis.shape[1]
    points = []
    
    import itertools
    ranges = [range(-range_limit, range_limit + 1) for _ in range(n)]
    
    for coeffs in itertools.product(*ranges):
        coeffs_array = np.array(coeffs)
        point = basis.T @ coeffs_array
        points.append(point)
    
    return np.array(points)

# Main execution
print("=" * 60)
print("Closest Vector Problem (CVP) Solver")
print("=" * 60)

# Define the 2D lattice basis
basis_2d = np.array([[3, 1],
                      [1, 2]])

target_2d = np.array([5.7, 3.2])

print("\nLattice Basis B:")
print(basis_2d)
print(f"\nTarget Point t: {target_2d}")

# Solve using Babai's algorithm
print("\n" + "=" * 60)
print("Method 1: Babai's Nearest Plane Algorithm (Fast Approximation)")
print("=" * 60)

start_time = time.time()
babai_point, babai_coeffs = babai_algorithm(basis_2d, target_2d)
babai_time = time.time() - start_time

babai_distance = np.linalg.norm(target_2d - babai_point)

print(f"Coefficients: {babai_coeffs}")
print(f"Closest Point (approx): {babai_point}")
print(f"Distance: {babai_distance:.6f}")
print(f"Computation Time: {babai_time:.6f} seconds")

# Solve using enumeration (exact solution)
print("\n" + "=" * 60)
print("Method 2: Exhaustive Enumeration (Exact Solution)")
print("=" * 60)

start_time = time.time()
exact_point, exact_coeffs, exact_distance = enumerate_cvp(basis_2d, target_2d, search_radius=10)
enum_time = time.time() - start_time

print(f"Coefficients: {exact_coeffs}")
print(f"Closest Point (exact): {exact_point}")
print(f"Distance: {exact_distance:.6f}")
print(f"Computation Time: {enum_time:.6f} seconds")

# 3D Example
print("\n" + "=" * 60)
print("3D Lattice Example")
print("=" * 60)

basis_3d = np.array([[4, 1, 0],
                      [1, 3, 1],
                      [0, 1, 3]])

target_3d = np.array([7.5, 5.2, 4.8])

print("\n3D Lattice Basis B:")
print(basis_3d)
print(f"\nTarget Point t: {target_3d}")

# Babai for 3D
print("\nBabai's Algorithm (3D):")
babai_point_3d, babai_coeffs_3d = babai_algorithm(basis_3d, target_3d)
babai_distance_3d = np.linalg.norm(target_3d - babai_point_3d)

print(f"Coefficients: {babai_coeffs_3d}")
print(f"Closest Point: {babai_point_3d}")
print(f"Distance: {babai_distance_3d:.6f}")

# Exact solution for 3D
print("\nExhaustive Enumeration (3D):")
start_time = time.time()
exact_point_3d, exact_coeffs_3d, exact_distance_3d = enumerate_cvp(basis_3d, target_3d, search_radius=5)
enum_time_3d = time.time() - start_time

print(f"Coefficients: {exact_coeffs_3d}")
print(f"Closest Point: {exact_point_3d}")
print(f"Distance: {exact_distance_3d:.6f}")
print(f"Computation Time: {enum_time_3d:.6f} seconds")

# Visualization
print("\n" + "=" * 60)
print("Generating Visualizations...")
print("=" * 60)

# Generate lattice points for 2D
lattice_points_2d = generate_lattice_points(basis_2d, range_limit=5)

# Generate lattice points for 3D
lattice_points_3d = generate_lattice_points(basis_3d, range_limit=3)

# Create comprehensive visualization
fig = plt.figure(figsize=(20, 12))

# 2D Plot - Overview
ax1 = fig.add_subplot(2, 3, 1)
ax1.scatter(lattice_points_2d[:, 0], lattice_points_2d[:, 1], 
           c='lightblue', s=50, alpha=0.6, label='Lattice Points')
ax1.scatter(target_2d[0], target_2d[1], 
           c='red', s=200, marker='*', label='Target', zorder=5)
ax1.scatter(exact_point[0], exact_point[1], 
           c='green', s=150, marker='s', label='Closest Point (Exact)', zorder=5)
ax1.scatter(babai_point[0], babai_point[1], 
           c='orange', s=150, marker='^', label='Babai Approximation', zorder=5)

# Draw basis vectors
origin = np.array([0, 0])
ax1.arrow(origin[0], origin[1], basis_2d[0, 0], basis_2d[1, 0], 
         head_width=0.3, head_length=0.3, fc='blue', ec='blue', linewidth=2, alpha=0.7)
ax1.arrow(origin[0], origin[1], basis_2d[0, 1], basis_2d[1, 1], 
         head_width=0.3, head_length=0.3, fc='purple', ec='purple', linewidth=2, alpha=0.7)

ax1.plot([target_2d[0], exact_point[0]], [target_2d[1], exact_point[1]], 
        'g--', linewidth=2, label=f'Distance: {exact_distance:.3f}')

ax1.set_xlabel('X', fontsize=12)
ax1.set_ylabel('Y', fontsize=12)
ax1.set_title('2D CVP: Lattice and Target Point', fontsize=14, fontweight='bold')
ax1.legend(fontsize=10)
ax1.grid(True, alpha=0.3)
ax1.axis('equal')

# 2D Plot - Zoomed in
ax2 = fig.add_subplot(2, 3, 2)
nearby_points = lattice_points_2d[
    (np.abs(lattice_points_2d[:, 0] - target_2d[0]) < 5) & 
    (np.abs(lattice_points_2d[:, 1] - target_2d[1]) < 5)
]
ax2.scatter(nearby_points[:, 0], nearby_points[:, 1], 
           c='lightblue', s=100, alpha=0.8, label='Nearby Lattice Points')
ax2.scatter(target_2d[0], target_2d[1], 
           c='red', s=300, marker='*', label='Target', zorder=5)
ax2.scatter(exact_point[0], exact_point[1], 
           c='green', s=200, marker='s', label='Closest Point', zorder=5)

for point in nearby_points:
    distance = np.linalg.norm(point - target_2d)
    ax2.plot([target_2d[0], point[0]], [target_2d[1], point[1]], 
            'gray', alpha=0.3, linewidth=1)
    
ax2.plot([target_2d[0], exact_point[0]], [target_2d[1], exact_point[1]], 
        'g-', linewidth=3, label=f'Min Distance: {exact_distance:.3f}')

ax2.set_xlabel('X', fontsize=12)
ax2.set_ylabel('Y', fontsize=12)
ax2.set_title('2D CVP: Zoomed View', fontsize=14, fontweight='bold')
ax2.legend(fontsize=10)
ax2.grid(True, alpha=0.3)
ax2.axis('equal')

# Distance comparison plot
ax3 = fig.add_subplot(2, 3, 3)
methods = ['Babai\n(Approx)', 'Enumeration\n(Exact)']
distances = [babai_distance, exact_distance]
colors = ['orange', 'green']
bars = ax3.bar(methods, distances, color=colors, alpha=0.7, edgecolor='black', linewidth=2)

for i, (bar, dist) in enumerate(zip(bars, distances)):
    height = bar.get_height()
    ax3.text(bar.get_x() + bar.get_width()/2., height,
            f'{dist:.4f}',
            ha='center', va='bottom', fontsize=12, fontweight='bold')

ax3.set_ylabel('Distance to Target', fontsize=12)
ax3.set_title('2D CVP: Method Comparison', fontsize=14, fontweight='bold')
ax3.grid(True, alpha=0.3, axis='y')

# 3D Plot - Main view
ax4 = fig.add_subplot(2, 3, 4, projection='3d')
ax4.scatter(lattice_points_3d[:, 0], lattice_points_3d[:, 1], lattice_points_3d[:, 2],
           c='lightblue', s=30, alpha=0.4, label='Lattice Points')
ax4.scatter(target_3d[0], target_3d[1], target_3d[2],
           c='red', s=300, marker='*', label='Target', zorder=5)
ax4.scatter(exact_point_3d[0], exact_point_3d[1], exact_point_3d[2],
           c='green', s=200, marker='s', label='Closest Point', zorder=5)
ax4.plot([target_3d[0], exact_point_3d[0]], 
        [target_3d[1], exact_point_3d[1]], 
        [target_3d[2], exact_point_3d[2]],
        'g-', linewidth=3, label=f'Distance: {exact_distance_3d:.3f}')

# Draw basis vectors
origin_3d = np.array([0, 0, 0])
for i in range(3):
    ax4.quiver(origin_3d[0], origin_3d[1], origin_3d[2],
              basis_3d[0, i], basis_3d[1, i], basis_3d[2, i],
              arrow_length_ratio=0.1, linewidth=2, alpha=0.7)

ax4.set_xlabel('X', fontsize=12)
ax4.set_ylabel('Y', fontsize=12)
ax4.set_zlabel('Z', fontsize=12)
ax4.set_title('3D CVP: Lattice Structure', fontsize=14, fontweight='bold')
ax4.legend(fontsize=10)
ax4.grid(True, alpha=0.3)

# 3D Plot - Different angle
ax5 = fig.add_subplot(2, 3, 5, projection='3d')
nearby_points_3d = lattice_points_3d[
    (np.abs(lattice_points_3d[:, 0] - target_3d[0]) < 6) & 
    (np.abs(lattice_points_3d[:, 1] - target_3d[1]) < 6) &
    (np.abs(lattice_points_3d[:, 2] - target_3d[2]) < 6)
]
ax5.scatter(nearby_points_3d[:, 0], nearby_points_3d[:, 1], nearby_points_3d[:, 2],
           c='lightblue', s=60, alpha=0.6, label='Nearby Lattice Points')
ax5.scatter(target_3d[0], target_3d[1], target_3d[2],
           c='red', s=300, marker='*', label='Target', zorder=5)
ax5.scatter(exact_point_3d[0], exact_point_3d[1], exact_point_3d[2],
           c='green', s=200, marker='s', label='Closest Point', zorder=5)
ax5.plot([target_3d[0], exact_point_3d[0]], 
        [target_3d[1], exact_point_3d[1]], 
        [target_3d[2], exact_point_3d[2]],
        'g-', linewidth=3)

ax5.set_xlabel('X', fontsize=12)
ax5.set_ylabel('Y', fontsize=12)
ax5.set_zlabel('Z', fontsize=12)
ax5.set_title('3D CVP: Zoomed View', fontsize=14, fontweight='bold')
ax5.legend(fontsize=10)
ax5.view_init(elev=20, azim=45)
ax5.grid(True, alpha=0.3)

# 3D Distance comparison
ax6 = fig.add_subplot(2, 3, 6)
methods_3d = ['Babai\n(Approx)', 'Enumeration\n(Exact)']
distances_3d = [babai_distance_3d, exact_distance_3d]
colors_3d = ['orange', 'green']
bars_3d = ax6.bar(methods_3d, distances_3d, color=colors_3d, alpha=0.7, edgecolor='black', linewidth=2)

for i, (bar, dist) in enumerate(zip(bars_3d, distances_3d)):
    height = bar.get_height()
    ax6.text(bar.get_x() + bar.get_width()/2., height,
            f'{dist:.4f}',
            ha='center', va='bottom', fontsize=12, fontweight='bold')

ax6.set_ylabel('Distance to Target', fontsize=12)
ax6.set_title('3D CVP: Method Comparison', fontsize=14, fontweight='bold')
ax6.grid(True, alpha=0.3, axis='y')

plt.tight_layout()
plt.savefig('cvp_analysis.png', dpi=300, bbox_inches='tight')
plt.show()

print("\nVisualization complete!")
print("=" * 60)

Code Explanation

1. Babai’s Nearest Plane Algorithm

The babai_algorithm function implements Babai’s rounding technique, which provides a polynomial-time approximation to CVP:

$$\mathbf{v}_{\text{approx}} = \mathbf{B} \cdot \lfloor \mathbf{B}^{-1} \mathbf{t} \rceil$$

where $\lfloor \cdot \rceil$ denotes rounding to the nearest integer. This algorithm:

• Computes the real-valued coefficients by solving $\mathbf{B}^T \mathbf{x} = \mathbf{t}$
• Rounds each coefficient to the nearest integer
• Reconstructs the lattice point using these integer coefficients

Time complexity: $O(n^3)$ where $n$ is the dimension.

2. Exhaustive Enumeration

The enumerate_cvp function finds the exact solution by checking all lattice points within a specified search radius. For each integer coefficient combination:

• Compute the lattice point: $\mathbf{v} = \mathbf{B}^T \mathbf{x}$
• Calculate distance: $d = |\mathbf{t} - \mathbf{v}|$
• Track the minimum distance

Time complexity: $O((2r+1)^n)$ where $r$ is the search radius and $n$ is the dimension. This becomes impractical for large dimensions, but provides exact solutions for small problems.

3. Lattice Point Generation

The generate_lattice_points function creates a grid of lattice points for visualization by systematically varying the integer coefficients within a specified range.

4. Visualization Components

The code generates six plots:

• 2D Overview: Shows the entire lattice structure with basis vectors, target point, and closest point
• 2D Zoomed View: Focuses on nearby lattice points and visualizes distances from multiple candidates
• 2D Method Comparison: Bar chart comparing Babai’s approximation vs. exact enumeration
• 3D Lattice Structure: Full 3D visualization with basis vectors
• 3D Zoomed View: Rotated view focusing on nearby points
• 3D Method Comparison: Performance comparison in 3D case

Results and Analysis

Execution Results

============================================================
Closest Vector Problem (CVP) Solver
============================================================

Lattice Basis B:
[[3 1]
 [1 2]]

Target Point t: [5.7 3.2]

============================================================
Method 1: Babai's Nearest Plane Algorithm (Fast Approximation)
============================================================
Coefficients: [2 1]
Closest Point (approx): [7 4]
Distance: 1.526434
Computation Time: 0.000772 seconds

============================================================
Method 2: Exhaustive Enumeration (Exact Solution)
============================================================
Coefficients: [2 0]
Closest Point (exact): [6 2]
Distance: 1.236932
Computation Time: 0.005535 seconds

============================================================
3D Lattice Example
============================================================

3D Lattice Basis B:
[[4 1 0]
 [1 3 1]
 [0 1 3]]

Target Point t: [7.5 5.2 4.8]

Babai's Algorithm (3D):
Coefficients: [2 1 1]
Closest Point: [9 6 4]
Distance: 1.878829

Exhaustive Enumeration (3D):
Coefficients: [2 0 2]
Closest Point: [8 4 6]
Distance: 1.769181
Computation Time: 0.042322 seconds

============================================================
Generating Visualizations...
============================================================
Visualization complete!
============================================================

The results demonstrate several important properties of CVP:

1. Babai’s approximation provides very fast solutions that are often optimal or near-optimal, especially for well-conditioned lattice bases.

2. Exact enumeration guarantees finding the optimal solution but has exponential complexity. For our 2D example with search radius 10, this checks $(2 \times 10 + 1)^2 = 441$ points.

3. Dimensionality impact: The 3D case requires significantly more computation for exact enumeration, highlighting why approximation algorithms are essential for higher dimensions.

4. Distance metrics: The $L^2$ norm (Euclidean distance) is used:
   $$d(\mathbf{t}, \mathbf{v}) = \sqrt{\sum_{i=1}^{n} (t_i - v_i)^2}$$

The visualizations clearly show how the lattice structure constrains possible solutions, and how the target point’s position relative to the lattice determines which lattice point is closest. The 3D plots provide intuitive understanding of how CVP extends to higher dimensions.