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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.