Paper 2024/714 Original: eprint.iacr.org/2024/714 ↗

Learning With Quantization: A Ciphertext Efficient Lattice Problem with Tight Security Reduction from LWE

Abstract

In this paper, we introduce Learning With Quantization (LWQ), a new problem related to the Learning With Errors (LWE) and Learning With Rounding (LWR) problems. LWQ provides a tight security reduction from LWE while enabling efficient ciphertext compression comparable to that of LWR. We adopt polar lattices to instantiate the quantizer of LWQ. Polar lattices are a specific instance of the classical Construction D, which utilizes a set of nested polar codes as component codes. Due to the polarization phenomenon of polar codes, the distribution of the quantization error converges to a discrete Gaussian. Moreover, the quantization algorithm can be executed in polynomial time. Our main result establishes a security reduction from LWE to LWQ, ensuring that the LWQ distribution remains computationally indistinguishable from the uniform distribution. The technical novelty lies in bypassing the noise merging principle often seen in the security reduction of LWR, instead employing a more efficient noise matching principle. We show that the compression rate is ultimately determined by the capacity of the ``LWE channel,'' which can be adjusted flexibly. Additionally, we propose a full information-rate encryption framework based on LWQ, demonstrating its advantage over constructions based on LWE and quantized LWE. Our result answers affirmatively a question left open by Micciancio and Schultz (CRYPTO 2023).