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
[ Cryptology ePrint archive ]