Cryptology ePrint Archive: Report 2022/093

Public-Key Encryption from Continuous LWE

Andrej Bogdanov and Miguel Cueto Noval and Charlotte Hoffmann and Alon Rosen

Abstract: 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.

Category / Keywords: public-key cryptography / public-key encryption, continuous learning with errors, statistical zero-knowledge, hypercontractivity, statistical-computational gaps, discrete gaussian sampling

Original Publication (in the same form): ArXiv, ECCC

Date: received 25 Jan 2022

Contact author: andrejb at cse cuhk edu hk, miguel cuetonoval at ist ac at, charlotte hoffmann at ist ac at, alon rosen at unibocconi it

Available format(s): PDF | BibTeX Citation

Version: 20220131:074235 (All versions of this report)

Short URL: ia.cr/2022/093