Good and bad bases of one lattice
The same grid of points from two bases. With a short basis, rounding finds the closest point; with a long, skewed one it fails.
|b₁| = 2.84|b₂| = 4.70det = 0.89Babai distance 2.57closest 0.31
Babai picked the filled point, but the ringed one is closer. With a skewed basis the rounding cell is long and thin, so it reaches far away. Drag t to see how often it fails.
What to notice
- Both bases generate exactly the same points. The volume of the parallelogram (the determinant) is the same too.
- Babai rounding with the bad basis lands far from t. The secret key of a lattice scheme is, in effect, a good basis.
- Gauss reduction turns the bad basis back into the good one in 2D. In hundreds of dimensions no known algorithm, classical or quantum, does this efficiently.