The task of converting a "bad" basis into a "good" basis in lattice theory is known as the basis reduction problem, and it is indeed computationally hard for general lattices. As mentioned in the question, a "bad" basis consists of long, non-orthogonal vectors that do not reveal much about the underlying lattice structure, while a "good" basis is composed of shorter, nearly orthogonal vectors, which makes solving certain lattice problems more efficient.
Why is Converting a Bad Basis to a Good Basis Hard?
Lattice basis reduction involves finding a basis where the vectors are short and almost orthogonal. This is crucial for solving difficult problems like the (approximate versions of ) Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). Both SVP and CVP are well-known to be computationally hard in high dimensions. These problems are inherently connected to finding better lattice bases because identifying short vectors or vectors closest to a point becomes much easier when using a good basis.
However, algorithms like the Lenstra-Lenstra-Lovász (LLL) algorithm, which is a polynomial-time algorithm for lattice basis reduction, only provide an approximate solution. The LLL algorithm guarantees that the basis vectors are within a certain approximation factor (exponential in the dimension) of the shortest possible vectors. While it is efficient for low dimensions and can reduce a bad basis somewhat, as the lattice's dimension increases, the approximation becomes less accurate. As a result, the LLL-reduced basis may still be far from a "good" basis in high dimensions, making it ineffective for extracting the private key.
There are more powerful algorithms such as BKZ (Block Korkin-Zolotarev), which offer better approximations by working on blocks of the lattice at a time. These algorithms improve upon LLL and can produce bases that are closer to the shortest basis (which is defined below). However, they are also much more computationally expensive than LLL, especially for large dimensions. These higher-cost algorithms are still approximate and do not solve the shortest basis problem exactly.
The Shortest Basis Problem (SBP)
A well-defined problem related to lattice basis reduction is the Shortest Basis Problem (SBP), which formalizes the task of finding the shortest possible basis for a lattice.
Given a basis $B = [b_1, \dots, b_n]$ for a lattice $\mathcal{L}$, find a basis $B' = [b_1', \dots, b_n']$ such that $B'$ is a basis of $\mathcal{L}$ and
$$\|B'\| = \min_{C \text{ is a basis of }\mathcal{L}} \|C\|$$
where $\|C\| = \underset{i \in [n]}{\max} \|c_i\|\;$.
This is a computationally hard problem like SVP and CVP.
