I am researching lattice problems and some methods for solving them. I read some books that mentioned Babai's algorithm for finding the Closest Vector Problem (CVP) cannot be successful with a "bad" basis for a lattice.
Which begs a question: what is the worst basis for a lattice?
Is the HNF basis the worst basis for finding CVP in a lattice?
Whether an algorithm succeeds or not for solving e.g. CVP depends on the quality of the basis, which for instance can be measured in terms of the sum of the norms of the basis vectors. Your question could therefore be interpreted as: does the HNF give you the basis of the lattice with the worst quality?
The answer has to be no to this. Suppose w.l.o.g. that the lattice lives in $\mathbb{Z}^n$, and the sum of the norms of the basis vectors of the HNF basis is $M$. Now clearly there can only be finitely many bases of the lattice for which this quality measure is less than $M$, as we can just enumerate all possible such bases. On the other hand, there are infinitely many bases for each lattice, and so there must be a basis with even worse quality. It all depends on how you define "quality", but for most sensible definitions there is no "worst quality" - you can always get a worse basis.
More concretely, given a basis matrix $B$, you can obtain another basis $B' = U \cdot B$ by multiplying $B$ with any unimodular matrix $U$. By taking a $U$ with huge entries, $B'$ will likely be a much worse basis than $B$.
There are two algorithms for CVP due to Babai. Nearest plane algorithm and the rounding algorithm. The former, first applies LLL. Therefore independent of the input basis, the algorithm will output the same vector. So your claim is not true (since this algorithm does not depend on the representation of the basis).
The latter algorithm, is the rounding algorithm of Babai. In this case indeed, the output depends on the input basis.
Your question is, if I feed the algorithm with an HNF-matrix, the output is worst if I use a better basis? In general no.
To see this, say that you have a full rank integer lattice and a basis which form a diagonal matrix, with positive integers in diagonal entries. This matrix is HNF and so the basis is an HNF-basis. But then, the rounding algorithm solves the CVP problem, since the basis is orthogonal (this is exercise 18.2.5). So again your claim does not seem true. Maybe, in specific lattices the HNF-basis provide bad results for CVP. But, you must be more specific.
The answer to your question depends on the context. If you are thinking in basis reductions of a lattice $L$, the answer is not really. HNF$(L)$ is of course difficult to reduce, but there is no reason to believe that HNF$(L)\times U$ where $U$ is a random unimodular matrix is easier to reduce than HNF($L$) (if that was the case, then to reduce any HNF just multiply by a random unimodular and reduce that!)
*Note that a lattice is determined uniquely by its HNF, so my notation HNF(L) is not ambiguous.
