Why does orthogonal basises makes it easier to solve SVP in lattices?

Question

I've been looking through https://courses.maths.ox.ac.uk/node/view_material/12662 and it mentions that:

Some bases make SVP easier:

• A “good” basis has shorter vector norms
• A “good” basis has nearly orthogonal vectors

I assume the reason for shorter vector norms being helpful is that there if we use an algorithm such as LLL, we will have a better starting point and that there will be less to reduce? However, I'm unsure exactly why nearly orthogonal basis vectors makes SVP easier. Is it only because it somehow makes it easier for algorithms such as LLL(-BKZ) to reduce the basis vectors?

Answer 1

Is it only because it somehow makes it easier for algorithms such as LLL(-BKZ) to reduce the basis vectors?

You have this somewhat backwards --- the point of basis reduction is to find a basis that is "shorter" and "more orthogonal", which you then use for useful applications.

Babai's nearest planes is a fairly well-known algorithm to solve an approximate form of CVP, that is defined relative to some fixed basis $B = [b_1,\dots,b_n]$ of a lattice. If $x\in\mathbb{R}^n$, and:

1. $v$ is the output of Babai's nearest planes, and
2. $v_{opt}$ is the closest vector to $x$,

then one can prove that: $$\lVert v-v_{opt}\rVert_2^2 \leq \frac{1}{4}\sum_{i = 1}^n \lVert b_i^*\rVert_2^2$$ where $\{b_1^*,\dots, b_n^*\}$ is the Gram-Schmidt orthogonalization of $B$. Note that as the Gram-Schmidt orthogonalization applies solely elementary operations, one has that:

$$\det([b_1^*,\dots, b_n^*]) = \det B$$

e.g. the total product $\prod_{i=1}^n \lVert b_i^*\rVert_2 = \det B$ is kept invariant. It should be easy to see that the error bound in Babai's nearest planes will be minimized if this "$\det B$ amount of mass" is "spread out evenly" through all of $\{b_1^*,\dots, b_n^*\}$, e.g. if the basis is short and nearly orthogonal.