NTL: Solve the closest vector problem for non-square matrix using LLL/Nearest Plane Algorithm

Assume I have a matrix $$A \in \mathbb{Z}^{m \times n}$$, $$m > n$$, which forms a basis of a lattice. Given a vector target vector $$t = Ax + e$$, $$t,e \in \mathbb{Z}^m$$,$$x \in \mathbb{Z}^n$$, I want to find the (approximate) closest vector in the lattice $$\mathcal{L}(A)$$ to $$t$$.

I wanted to use Babai's nearest plane algorithm, in particular the NTL implementation NTL::NearVector to solve this problem (approximately) using LLL. However, it seems to me that in the literature and definitely in the software package, Babai's nearest plane algorithm requires a full-rank lattice?

What other techniques/embeddings can I use to solve the closest vector problem on an lattice with higher dimension than rank? Could I just extend the matrix with zero-vector columns?

• In the $\ell_2$ norm, it should suffice to project your vector onto the (real) span of your lattice (which is a rank $n$ subspace), then orthogonally rotate this subspace to be isomorphic to $\mathbb{R}^n\times\{0\}^{m-n}$. I don't know how to do this in NTL in though, so will only leave the comment.
– Mark
Sep 28 '21 at 20:45