Public-Key Encryption from Homogeneous CLWE

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

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

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in TCC 2022
Keywords: 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
History: 2022-11-07: revised; 2022-01-31: received; See all versions
Short URL: https://ia.cr/2022/093
License: CC BY

BibTeX

@misc{cryptoeprint:2022/093,
      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{https://eprint.iacr.org/2022/093}},
      url = {https://eprint.iacr.org/2022/093}
}