Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures

Understand

We show direct and conceptually simple reductions between the classical learning with errors (LWE) problem and its continuous analog, CLWE (Bruna, Regev, Song and Tang, STOC 2021).

• This allows us to bring to bear the powerful machinery of LWE-based cryptography to the applications of CLWE.
• For example, we obtain the hardness of CLWE under the classical worst-case hardness of the gap shortest vector problem.
• Previously, this was known only under quantum worst-case hardness of lattice problems.