Paper 2026/650

LWE is as Hard as Continuous LWE \& a Search-to-Decision Reduction

Abstract

In 2021, Bruna, Regev, Song and Tang introduced the continuous analogue of LWE, CLWE. Shortly after, Gupte, Vafa, and Vaikuntanathan showed a classical reduction from LWE to CLWE and from discrete-CLWE (secret from a discrete set) to LWE. In this paper, we show two results. The first result is a search-to-decision reduction for CLWE. The search-to-decision reduction works similarly to the standard reduction for LWE. The main difference between the reductions is the continuous nature of the CLWE secret. As a consequence, our reduction can find the secret up to a polynomial error $n^{-k}$ for some constant $k$. The second and our main result is the reduction from CLWE to discrete-CLWE. The reduction is an identity reduction, i.e. samples are passed as-is to the distinguisher. To prove the distinguisher can accept the samples we employ tools from analytic number theory. These tools allow us to show that the set $\frac{1}{r} \cdot \mathbb{Z}^n$ with fixed $\ell_2$ norm $r$, i.e. integer vectors projected onto the unit sphere, can mimic the unit sphere $S^{n-1}$ for some $r > r'$. By completing this missing link, we can show that LWE is equivalent to CLWE i.e. $\text{LWE} \equiv \text{CLWE}$ and existing or new results on each problem apply to the other.