Paper 2024/714

Learning with Quantization: Construction, Hardness, and Applications

Shanxiang Lyu, Jinan University
Ling Liu, Xidian University
Cong Ling, Imperial College London
Abstract

This paper presents a generalization of the Learning With Rounding (LWR) problem, initially introduced by Banerjee, Peikert, and Rosen, by applying the perspective of vector quantization. In LWR, noise is induced by scalar quantization. By considering a new variant termed Learning With Quantization (LWQ), we explore large-dimensional fast-decodable lattices with superior quantization properties, aiming to enhance the compression performance over scalar quantization. We identify polar lattices as exemplary structures, effectively transforming LWQ into a problem akin to Learning With Errors (LWE), whose distribution of quantization error is statistically close to discrete Gaussian. We present two applications of LWQ: Lily, a smaller ciphertext public key encryption (PKE) scheme, and quancryption, a privacy-preserving secret-key encryption scheme. Lily achieves smaller ciphertext sizes without sacrificing security, while quancryption achieves a source-ciphertext ratio larger than $1$.

Note: Updated security proof.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Lattice-Based CryptographyLearning with QuantizationPolar LatticeCiphertext Compression
Contact author(s)
lsx07 @ jnu edu cn
liuling @ xidian edu cn
c ling @ imperial ac uk
History
2024-05-27: revised
2024-05-09: received
See all versions
Short URL
https://ia.cr/2024/714
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/714,
      author = {Shanxiang Lyu and Ling Liu and Cong Ling},
      title = {Learning with Quantization: Construction, Hardness, and Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/714},
      year = {2024},
      url = {https://eprint.iacr.org/2024/714}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.