Timeline for Can i use Babai algorithm in q-ary lattice
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 14, 2023 at 10:07 | vote | accept | Mike Anast | ||
| Jul 13, 2018 at 12:54 | comment | added | Hilder Vitor Lima Pereira | 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). | |
| Jul 12, 2018 at 9:16 | comment | added | Mike Anast | 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}$. | |
| Jul 11, 2018 at 15:06 | history | edited | Hilder Vitor Lima Pereira | CC BY-SA 4.0 | Improved explanation. |
| Jul 11, 2018 at 15:02 | history | undeleted | Hilder Vitor Lima Pereira | ||
| Jul 11, 2018 at 15:00 | history | deleted | Hilder Vitor Lima Pereira | via Vote | |
| Jul 11, 2018 at 15:00 | history | answered | Hilder Vitor Lima Pereira | CC BY-SA 4.0 |