IEEE International Symposium on Information Theory (ISIT)
Towards Ciphertext-Efficient LWE: Learning With Sampling over Sublattices
Shanxiang Lyu, Ling Liu, Yong Li, Linqi Song
Abstract
The samples of Learning With Errors (LWE) are in the form (A, b = As + e), where e admits a discrete Gaussian that resides over ${{\mathbb{Z}}^m}$, and ${\text{b}} \in {\mathbb{Z}}_q^m$. To reduce the size of b, this paper presents a ciphertext-efficient primitive called Learning With Sampling (LWS). Let ${\text{Q}} \subset {{\mathbb{Z}}^m}$ be a sublattice, the samples of LWS are (${\text{A}},{\text{b}} = {\text{As}} + {{\text{e}}_S}$), where ${{\text{e}}_S}$ admits a discrete Gaussian that resides over the coset Q-As. Conditioned on the randomness of As, we show that the quantization error ${{\text{e}}_S}$ amounts to the discrete Gaussian error e used in LWE, as long as the sampling width tailored to exceed the smoothing parameter of the lattice Q. Consequently, this ensures negligible difference between e and ${{\text{e}}_S}$. We provide computational and information-theoretic proofs to establish the hardness of search and decision variants of LWS. We demonstrate that LWS can effectively replace LWE in public key encryption (PKE), moderately reducing ciphertext size while maintaining security.