• Mon, 04 Apr 2022 13:00 Public-Key Encryption from Continuous LWE by Charlotte Hoffmann (IST Austria)

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.

This is joint work with Andrej Bogdanov, Miguel Cueto Noval and Alon Rosen. E-print: https://eprint.iacr.org/2022/093

Speaker Bio:

Charlotte is a PhD student in the Cryptography group at IST Austria under the supervision of Krzysztof Pietrzak.

Venue: Online