Here are three example sets of basis vectors for 2D and 3D lattice Shortest Vector Problems (SVP). Each set of vectors defines a lattice; the “problem” is to find the shortest non-zero vector that can be formed by an integer combination of these basis vectors.
2D Lattice SVP Examples
A 2D lattice is defined by a basis of two vectors, and .
Example 1: Orthogonal Basis (The “Easy” Case)
This is the simplest lattice, where the basis vectors are already short and perpendicular.
This basis generates the standard integer grid . The shortest non-zero vectors are obviously , , and their negatives, all with a length of 1.
Example 2: Slightly Skewed Basis
This example shows how the shortest vector isn’t always one of the basis vectors.
The basis vectors have lengths and . However, a shorter vector can be found by combining them: The length of is , which is the shortest vector in this lattice.
Example 3: Highly Skewed Basis (The “Hard” Case)
This is a “bad” basis, where the vectors are long and nearly parallel. Finding the short vector is non-trivial and demonstrates why reduction algorithms like LLL are needed.
Both basis vectors are very long (length ). But a simple integer combination reveals a tiny vector: The length of is .
3D Lattice SVP Examples
A 3D lattice is defined by a basis of three vectors, , , and .
Example 1: Orthogonal Basis
Similar to the 2D case, this is the standard integer lattice.
The shortest non-zero vectors have a length of 1.
Example 2: Symmetric, Non-Orthogonal Basis
This is a non-trivial but structured lattice.
The basis vectors are relatively long (length ). The shortest vector is not immediately obvious from this basis. (For reference, a short vector in this lattice is , which can be formed by a combination like ).
Example 3: Highly Skewed “Bad” Basis
This is a classic example used to show the power of the LLL algorithm. The basis vectors are enormous and almost orthogonal, yet they hide a very short vector.
The shortest vector in this lattice is , which has a length of . This vector is found using a massive integer combination: