Paper 2022/093

Public-Key Encryption from Homogeneous CLWE

Andrej Bogdanov, Chinese University of Hong Kong
Miguel Cueto Noval, Institute of Science and Technology Austria
Charlotte Hoffmann, Institute of Science and Technology Austria
Alon Rosen, Bocconi University, Reichman University

The homogeneous continuous LWE (hCLWE) problem is to distinguish samples of a specific high-dimensional Gaussian mixture from standard normal samples. It was shown to be at least as hard as Learning with Errors, but no reduction in the other direction is currently known. We present four new public-key encryption schemes based on the hardness of hCLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Our schemes yield a polynomial-time algorithm for solving hCLWE using a Statistical Zero-Knowledge oracle.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in TCC 2022
public-key encryption continuous learning with errors statistical zero-knowledge hypercontractivity statistical-computational gaps discrete gaussian sampling
Contact author(s)
andrejb @ cse cuhk edu hk
miguel cuetonoval @ ist ac at
charlotte hoffmann @ ist ac at
alon rosen @ unibocconi it
2022-11-07: revised
2022-01-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andrej Bogdanov and Miguel Cueto Noval and Charlotte Hoffmann and Alon Rosen},
      title = {Public-Key Encryption from Homogeneous CLWE},
      howpublished = {Cryptology ePrint Archive, Paper 2022/093},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.