LWE

• It was presented in the paper [REGEV09], where it was denoted by $LWE_{p, \chi}$, meaning that equations (vectors $a_i$) would be sampled from $\mathbb{Z}_p$ and errors (values $e_i$) would be sampled from $\chi$.


• Decision version and Search version are polynomially equivalent if $p$ is prime. [REGEV09 - Lemma 4.2]


• A poly-time algorithm to solve $LWE_{p, \Psi_\alpha}$ implies in a poly-time quantum algorithm to $GapSVP$.

In [REGEV09], lemma 3.20 reduces $DGS_{\sqrt{n}\gamma{(n)} / \lambda_1(L^*)}$ to $GapSVP_{100\sqrt{n}\gamma{(n)}}$ and theorem 3.1 (quantum) reduces $DGS_{\sqrt{2n}\eta_\epsilon(L) / \alpha}$ to $LWE_{p, \Psi_\alpha}$ for $0 < \alpha < 1$ and $\alpha \cdot p < 2\sqrt{n}$



• A poly-time algorithm to solve $LWE_{p, \Psi_\alpha}$ implies in a poly-time quantum algorithm to $SIVP$

In [REGEV09], lemma 3.17 reduces $DGS_{\gamma{(n)}}$ to $GIVP_{2\sqrt{n}\phi{(L)}}$ (GIVP is a generalization of SIVP) and theorem 3.1 (quantum) reduces $DGS_{\sqrt{2n}\eta_\epsilon(L) / \alpha}$ to $LWE_{p, \Psi_\alpha}$ for $0 < \alpha < 1$ and $\alpha \cdot p < 2\sqrt{n}$



• TODO: Include non-quantum reductions to Lattice problems.

References

• [REGEV09] On Lattices, Learning with Errors,Random Linear Codes, and Cryptography. (2009)