# Can i use Babai algorithm in q-ary lattice

Let's assume we have the q-ary lattice

$$\mathcal{L}_q({\bf A})=\{ {\bf z}\in \mathbb{Z}^{n} : \exists {\bf s}\in \mathbb{Z}^{n}_{q} \ , \ {\bf z}={\bf A s}^{T} \mod q \},$$

where ${\bf A}\in \mathbb{Z}^{n\times n}_{q}$.

My question is, can I use the Babai's algorithm with input the matrix ${\bf A}$ and a target vector ${\bf t}\in \mathbb{Z}_{q}^{n}$, to find a close lattice vector to ${\bf t}$ ?

Babai's Nearest Plane Algorithm is supposed to receive a basis of the lattice, and $\mathbf{A}$ is not the basis of the modular lattice that it spans. If you give Babai's algorithm the matrix ${\bf A}$, it will work over the lattice $\mathcal{L}({\bf A}) := \{ {\bf A}{\bf x} : {\bf x} \in \mathbb{Z}^n \}$ instead of $\mathcal{L}_q({\bf A})$. Therefore, it will probably output wrong answers.
For instance, if you take a vector $\mathbf{t} = (q, q, ..., q)$, then $\mathbf{t} \in \mathcal{L}_q({\bf A})$, therefore, Babai's algorithm must output $\mathbf{t}$ itself. But it is likely that $\mathbf{t} \not \in \mathcal{L}({\bf A})$, so, Babai's algorithm will output some vector different from ${\bf t}$.
• Thank you for your answer. I specifically want to solve LWE by reducing it to BDD problem. Lindner and Peikert in [web.eecs.umich.edu/~cpeikert/pubs/lwe-analysis.pdf] (page 11) assume, that we can view an LWE instance $({\bf A},{\bf t}={\bf A}^{T}{\bf s}+{\bf e})$ as a BDD problem in the lattice $\mathcal{L}_{q}({\bf A}^T)$. We can use the Babai algorithm with input a basis ${\bf B}$ of a lattice $\mathcal{L}_{q}({\bf A}^T)$ and a target vector ${\bf t}={\bf A}^{T}{\bf s}+{\bf e}$. Then Babai is able to find a lattice vector ${\bf v}$ such that ${\bf t}={\bf v}+{\bf e}$. – Mike Anast Jul 12 '18 at 9:16
• Hi, Mike. I see your point. But even in that particular case, I think you have to give Babai's algorithm the basis instead of ${\bf A}$. For instance, consider the following diagonal matrix ${\bf A}$ with diagonal $(5, 2)$, $q = 5$, ${\bf v} = (5, 5) \in \mathcal{L}({\bf A})_q$, and ${\bf e} = (1, 0)$. Then, Babai's algorithm should output ${\bf v}$, but if you pass ${\bf A}$ instead of the basis, it will probably output either $(5, 4)$ or $(0, 1)$ depending on how you represent ${\bf t}$ (as $(6, 5)$ or as $(1, 0)$, which is reduced mod 5). – Hilder Vitor Lima Pereira Jul 13 '18 at 12:54