International Association for Cryptologic Research

International Association
for Cryptologic Research


Public-Key Encryption from Homogeneous CLWE

Andrej Bogdanov , Chinese University of Hong Kong
Miguel Cueto Noval , IST Austria
Charlotte Hoffmann , IST Austria
Alon Rosen , Bocconi University and Reichman University
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2022
Abstract: 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.
  title={Public-Key Encryption from Homogeneous CLWE},
  author={Andrej Bogdanov and Miguel Cueto Noval and Charlotte Hoffmann and Alon Rosen},