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$
    – Mike Anast
    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$
    – Hilder Vitor Lima Pereira
    Jul 13, 2018 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.