Common Notation

Continuous LWE implied

Propose Edit

Updated:

Continuous LWE (CLWE) was introduced as the continuous analogue of LWE in 2021 by Bruna, Regev, Song, and Tang [1]. The problem samples \(\mat{A}\) from a normal distribution \(\mathcal{N}(0,1)\), restricts the secret \(\vec{s}\) to be a unit-vector in \(\RR^n\) and usually samples the error \(\vec{e}\) from another normal distribution.

Definition

Let \(S^{n-1}\) be the \(n-1\) unit sphere, i.e. all unit vectors in \(\RR^n\), and let \(\mathcal{N}(0,\alpha)\) denote the continuous normal / Gaussian distribution centered around \(0\) with Gaussian parameter \(\alpha\).

Continuous LWE\(_{n,m,\beta,\gamma}\)

Sample \(\mat{A} \sample \mathcal{N}(0, 1)^{m \times n}\), \(\vec{s} \sample S^{n-1}\), \(\vec{e} \sample \mathcal{N}(0, \beta^2)^m\), and \(\vec{u} \sample \mathcal{U}([0,1))^m\). An adversary is asked to distinguish between the distribution

\[\left( \mat{A}, \gamma \cdot \mat{A} \cdot \vec{s} + \vec{e} \bmod 1 \right) \text{ and } \left( \mat{A}, \vec{u} \right).\]

Note that we follow the definition given in [2].

Variants

Homogeneous Continuous LWE\(_{n,m,\beta,\gamma}\)

Sample \(\vec{k} \in \ZZ^{m}\) with each entry sampled with probability proportional to \(\exp(-k^2/2\gamma^2 + 2\beta^2)\). Sample \(\vec{s} \sample S^{n-1}\), and \(\vec{e} \sample \mathcal{N}(0, (\beta^2 / (\gamma^2 + \beta^2))^2)^m\). Further, sample \(\mat{A} \sample \mathcal{N}(0, 1)^{n \times m}\) conditioned on each column \(\vec{a}_i \perp \vec{s}\) being orthogonal to \(\vec{s}\). An adversary is asked to distinguish between the distribution

\[\mat{A} + \vec{s} \cdot \left( \frac{(\gamma^2 + \beta^2)}{\gamma} \cdot \vec{k}^T + \vec{e}^T \right) \bmod 1 \text{ and } \mathcal{N}(0,1)^{n \times m}.\]

Homogeneous Continuous LWE (HCLWE) was introduced alongside CLWE in [1]. The authors provide a polynomial-time quantum reduction from the Bounded Distance Decoding problem to HCLWE in Corollary 4.2. Further, they introduce a multi-version of HCLWE with a multitude of orthonormal secrets, which they call m-Homogeneous Continuous LWE, in Section 9 of [1], as well as a truncated version of the problem called Truncated Homogeneous Continuous LWE.

Hardness

Bruna et al. provide a ppt (classical) reduction from the Bounded Distance Decoding problem to CLWE in Lemma 3.3 of [1]. Further, Gupte, Vafa, and Vaikuntanathan show that CLWE is at least as hard as LWE in Corollary 5 of [3]. They utilise a version of LWE with fixed norm of the secret as an intermediate step, which they call fixed-norm LWE (Theorem 6 and Theorem 7). Furthermore, the authors provide a reduction from discrete-secret CLWE to LWE as well as a search-to-decision reduction for discrete-secret CLWE. The latter reduction is provided for the original, non-discrete version of CLWE in [4].

Constructions built from Continuous LWE

  • Public-Key Encryption [2]

References

  • [1]Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang. 2021. Continuous LWE. In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, 2021. ACM, 694–707. Retrieved from https://arxiv.org/abs/2005.09595
  • [2]Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, and Alon Rosen. 2022. Public-Key Encryption from Continuous LWE. Electron. Colloquium Comput. Complex. TR22, (2022). Retrieved from https://ia.cr/2022/093
  • [3]Aparna Gupte, Neekon Vafa, and Vinod Vaikuntanathan. 2022. Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, 2022. IEEE, 1162–1173. Retrieved from https://ia.cr/2022/437
  • [4]Kirpa Prince. 2026. A Search-to-Decision Reduction for Continuous LWE. Retrieved from https://ia.cr/2026/650