1
$\begingroup$

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}$ ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

No, you can'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}$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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}$. $\endgroup$ Commented Jul 12, 2018 at 9:16
  • $\begingroup$ 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). $\endgroup$ Commented Jul 13, 2018 at 12:54

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.