Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-011 | 25th January 2022 19:56

Public-Key Encryption from Continuous LWE



The continuous learning with errors (CLWE) problem was recently introduced by Bruna
et al. (STOC 2021). They showed that its hardness implies infeasibility of learning Gaussian
mixture models, while its tractability implies efficient Discrete Gaussian Sampling and thus
asymptotic improvements in worst-case lattice algorithms. No reduction between CLWE and
LWE is currently known, in either direction.
We propose four public-key encryption schemes based on the hardness of CLWE, with varying
tradeoffs between decryption and security errors, and different discretization techniques. Some
of our schemes are based on hCLWE, a homogeneous variant, which is no easier than CLWE.
Our schemes yield a polynomial-time algorithm for solving hCLWE, and hence also CLWE,
using a Statistical Zero-Knowledge oracle.

ISSN 1433-8092 | Imprint