Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Towards Ciphertext-Efficient LWE: Learning With Sampling over Sublattices

Shanxiang Lyu, Ling Liu, Yong Li, Linqi Song

Published Jun 1, 2026• 0 citations
Publisher

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.

DOI
10.1109/isit62367.2026.11653664

Related papers

Provably Secure LWE Encryption with Smallish Uniform Noise and Secret

Daniel Cabarcas, Florian Göpfert, Patrick Weiden

Abstract. In this paper we propose the first provably secure public key encryption scheme based on the Learning with Errors (LWE) problem, in which secrets and errors are sampled uniformly at random from a relatively small set rather than from the commonly used discrete Gaussian distribution. Using a uniform distribution, instead of a Gaussian, has the potential of improving computational efficiency a great deal due to its simplicity, thus making the scheme attractive for use in practice. At the same time our scheme features the strong security guarantee of being based on the hardness of worst-case lattice problems. After presenting the construction of our scheme we prove its security and propose asymptotic parameters. Finally, we compare our scheme on several measures to one of the most efficient LWE-based encryption schemes with Gaussian noise. We show that the expected efficiency improvement is debunked, due to the large blow-up of the parameter sets involved.

•Jan 1, 2014•2 citations

Provably Secure LWE-Encryption with Uniform Secret

Daniel Cabarcas, Florian Göpfert, Patrick Weiden

In this paper we propose the first provably secure public key encryption scheme based on the Learning with Errors (LWE) problem, in which secrets and errors are sampled uniformly at random from a relatively small set rather than from the commonly used discrete Gaussian distribution.Using a uniform distribution, instead of a Gaussian, has the potential of improving computational efficiency a great deal due to its simplicity, thus making the scheme attractive for use in practice.At the same time our scheme features the strong security guarantee of being based on the hardness of worst-case lattice problems.After presenting the construction of our scheme we prove its security and propose asymptotic parameters.Finally, we compare our scheme on several measures to one of the most efficient LWE-based encryption schemes with Gaussian noise.We show that the expected efficiency improvement is debunked, due to the large blow-up of the parameter sets involved.

•Mar 21, 2013•1 citation

Feasibility Analysis and Optimization of Non-Gaussian Error Distributions in LWE-based Cryptosystems: A Step Distribution Approach

Rongxun Yao

The Learning with Errors (LWE) problem is a fundamental hardness assumption for post-quantum lattice-based cryptography. Standard LWE schemes rely on discrete Gaussian error distributions, which incur high sampling overhead. This paper explores the feasibility of replacing the Gaussian distribution with a novel non-Gaussian alternative—the Step Distribution—within Regev’s classic LWE public-key encryption scheme. The Step Distribution partitions the error range into equal-width steps, with probabilities proportional to Gaussian weights at step midpoints. The distribution is formally defined, its asymptotic convergence to the discrete Gaussian is proved, and conditions under which the decryption error probability becomes negligible are derived. The Step Distribution offers a tunable parameter—the number of steps—that allows a trade-off between security (closeness to the Gaussian) and computational efficiency. This work provides a flexible error distribution for LWE-based cryptosystems, particularly suitable for resource-constrained environments.

Frontiers in Computing and Intelligent Systems•Jul 30, 2026•0 citations

Provably secure LWE encryption with smallish uniform noise and secret

Daniel Cabarcas, Florian Göpfert, Patrick Weiden

In this paper we propose the first provably secure public key encryption scheme based on the Learning with Errors (LWE) problem, in which secrets and errors are sampled uniformly at random from a relatively small set rather than from the commonly used discrete Gaussian distribution. Using a uniform distribution, instead of a Gaussian, has the potential of improving computational efficiency a great deal due to its simplicity, thus making the scheme attractive for use in practice. At the same time our scheme features the strong security guarantee of being based on the hardness of worst-case lattice problems. After presenting the construction of our scheme we prove its security and propose asymptotic parameters. Finally, we compare our scheme on several measures to one of the most efficient LWE-based encryption schemes with Gaussian noise. We show that the expected efficiency improvement is debunked, due to the large blow-up of the parameter sets involved.

ACM ASIA Public-Key Cryptography Workshop (APKC)•May 30, 2014•10 citations

New variant for Learning with Errors Problem

Xuyang Wang, Aiqun Hu, Hao Fang

The Learning with Errors (LWE) problem is a special average-case lattice problem, which has proved to be as hard as worst-case lattice problems. By this property, it has become the cornerstones for a series of cryptographic applications under the security assumption of worst-case lattice problems. However, the efficiency of these applications are not high. Therefore, how to improve the efficiency of cryptographic applications based on LWE is an urgent problem to be solved. In this paper, a new variant of LWE is proposed. By using trapdoor composed by lattice-based matrix and its dual orthogonal matrix, we construct a more efficient public key encryption (PKE) scheme based on the variant. Furthermore, by the hardness of the variant problem, we prove the new PKE scheme is chosen plaintext attack (CPA) secure. At last, we analyze the homomorphism property of the new PKE scheme.

Procedia Computer Science•Jan 1, 2018•3 citations

Leaky LWE: Learning with Errors with Semi-Adaptive Secret- and Error-Leakage

Russell W. F. Lai, Monisha Swarnakar, Ivy K. Y. Woo

The Learning with Errors (LWE) problem asks to distinguish noisy samples s^T A + e^T mod q from uniformly random values given the random matrix A. In this work, we show that a variant called Leaky LWE, where the distinguisher receives additionally noisy leakages (s^T, e^T) L + f^T of the LWE secret s and error e for low-norm matrix L chosen adaptively by the distinguisher after seeing A, is not easier than the standard LWE of the same dimensions up to polynomial losses in the noise level and the modulus. More generally, we show that the Leaky LWE problem is hard even if the public matrix A is structured and/or hinted and if the non-leaky parts of the secret and error do not follow Gaussian distributions, as long as the corresponding LWE problem without leakage is hard. Our reduction from LWE to Leaky LWE unifies and extends prior results on the Error-Leakage LWE problem [Döttling-Kolonelos-Lai-Lin-Malavolta-Rahimi, EUROCRYPT'23], where L only acts on the error e and the Hint-MLWE problem [Kim-Lee-Seo-Song, CRYPTO'23], where L is restricted to concatenations of random Gaussian scalar matrices not controlled by the distinguisher. Previously, the Hint-MLWE and Error-Leakage LWE assumptions were used as computational replacements of the statistical noise flooding technique in security proofs which led to improved parameters in lattice-based cryptographic constructions such as zero-knowledge proofs, threshold signatures and registration-based encryption. We provide lemmas which abstract out such computational arguments based on Leaky LWE.

IACR Communications in Cryptology•Oct 6, 2025•5 citations
The samples of Learning With Errors (LWE) are in the form (A, b = As + e), where e admits a discrete Gaussian that resides over Zm{{\mathbb{Z}}^m}Zm, and b∈Zqm{\text{b}} \in {\mathbb{Z}}_q^mb∈Zqm​. To reduce the size of b, this paper presents a ciphertext-efficient primitive called Learning With Sampling (LWS). Let Q⊂Zm{\text{Q}} \subset {{\mathbb{Z}}^m}Q⊂Zm be a sublattice, the samples of LWS are (A,b=As+eS{\text{A}},{\text{b}} = {\text{As}} + {{\text{e}}_S}A,b=As+eS​), where eS{{\text{e}}_S}eS​ admits a discrete Gaussian that resides over the coset Q-As. Conditioned on the randomness of As, we show that the quantization error eS{{\text{e}}_S}eS​ 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 eS{{\text{e}}_S}eS​. 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.
Abstract. In this paper we propose the first provably secure public key encryption scheme based on the Learning with Errors (LWE) problem, in which secrets and errors are sampled uniformly at random from a relatively small set rather than from the commonly used discrete Gaussian distribution. Using a uniform distribution, instead of a Gaussian, has the potential of improving computational efficiency a great deal due to its simplicity, thus making the scheme attractive for use in practice. At the same time our scheme features the strong security guarantee of being based on the hardness of worst-case lattice problems. After presenting the construction of our scheme we prove its security and propose asymptotic parameters. Finally, we compare our scheme on several measures to one of the most efficient LWE-based encryption schemes with Gaussian noise. We show that the expected efficiency improvement is debunked, due to the large blow-up of the parameter sets involved.
In this paper we propose the first provably secure public key encryption scheme based on the Learning with Errors (LWE) problem, in which secrets and errors are sampled uniformly at random from a relatively small set rather than from the commonly used discrete Gaussian distribution.Using a uniform distribution, instead of a Gaussian, has the potential of improving computational efficiency a great deal due to its simplicity, thus making the scheme attractive for use in practice.At the same time our scheme features the strong security guarantee of being based on the hardness of worst-case lattice problems.After presenting the construction of our scheme we prove its security and propose asymptotic parameters.Finally, we compare our scheme on several measures to one of the most efficient LWE-based encryption schemes with Gaussian noise.We show that the expected efficiency improvement is debunked, due to the large blow-up of the parameter sets involved.
The Learning with Errors (LWE) problem is a fundamental hardness assumption for post-quantum lattice-based cryptography. Standard LWE schemes rely on discrete Gaussian error distributions, which incur high sampling overhead. This paper explores the feasibility of replacing the Gaussian distribution with a novel non-Gaussian alternative—the Step Distribution—within Regev’s classic LWE public-key encryption scheme. The Step Distribution partitions the error range into equal-width steps, with probabilities proportional to Gaussian weights at step midpoints. The distribution is formally defined, its asymptotic convergence to the discrete Gaussian is proved, and conditions under which the decryption error probability becomes negligible are derived. The Step Distribution offers a tunable parameter—the number of steps—that allows a trade-off between security (closeness to the Gaussian) and computational efficiency. This work provides a flexible error distribution for LWE-based cryptosystems, particularly suitable for resource-constrained environments.
In this paper we propose the first provably secure public key encryption scheme based on the Learning with Errors (LWE) problem, in which secrets and errors are sampled uniformly at random from a relatively small set rather than from the commonly used discrete Gaussian distribution. Using a uniform distribution, instead of a Gaussian, has the potential of improving computational efficiency a great deal due to its simplicity, thus making the scheme attractive for use in practice. At the same time our scheme features the strong security guarantee of being based on the hardness of worst-case lattice problems. After presenting the construction of our scheme we prove its security and propose asymptotic parameters. Finally, we compare our scheme on several measures to one of the most efficient LWE-based encryption schemes with Gaussian noise. We show that the expected efficiency improvement is debunked, due to the large blow-up of the parameter sets involved.
The Learning with Errors (LWE) problem is a special average-case lattice problem, which has proved to be as hard as worst-case lattice problems. By this property, it has become the cornerstones for a series of cryptographic applications under the security assumption of worst-case lattice problems. However, the efficiency of these applications are not high. Therefore, how to improve the efficiency of cryptographic applications based on LWE is an urgent problem to be solved. In this paper, a new variant of LWE is proposed. By using trapdoor composed by lattice-based matrix and its dual orthogonal matrix, we construct a more efficient public key encryption (PKE) scheme based on the variant. Furthermore, by the hardness of the variant problem, we prove the new PKE scheme is chosen plaintext attack (CPA) secure. At last, we analyze the homomorphism property of the new PKE scheme.
The Learning with Errors (LWE) problem asks to distinguish noisy samples s^T A + e^T mod q from uniformly random values given the random matrix A. In this work, we show that a variant called Leaky LWE, where the distinguisher receives additionally noisy leakages (s^T, e^T) L + f^T of the LWE secret s and error e for low-norm matrix L chosen adaptively by the distinguisher after seeing A, is not easier than the standard LWE of the same dimensions up to polynomial losses in the noise level and the modulus. More generally, we show that the Leaky LWE problem is hard even if the public matrix A is structured and/or hinted and if the non-leaky parts of the secret and error do not follow Gaussian distributions, as long as the corresponding LWE problem without leakage is hard. Our reduction from LWE to Leaky LWE unifies and extends prior results on the Error-Leakage LWE problem [Döttling-Kolonelos-Lai-Lin-Malavolta-Rahimi, EUROCRYPT'23], where L only acts on the error e and the Hint-MLWE problem [Kim-Lee-Seo-Song, CRYPTO'23], where L is restricted to concatenations of random Gaussian scalar matrices not controlled by the distinguisher. Previously, the Hint-MLWE and Error-Leakage LWE assumptions were used as computational replacements of the statistical noise flooding technique in security proofs which led to improved parameters in lattice-based cryptographic constructions such as zero-knowledge proofs, threshold signatures and registration-based encryption. We provide lemmas which abstract out such computational arguments based on Leaky LWE.