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

Journal of Cryptology

On the Hardness of Module Learning with Errors with Short Distributions

Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, Weiqiang Wen

Published Nov 30, 2022• 36 citations
Publisher

Abstract

The Module Learning With Errors ( $$\text {M-LWE}$$ ) problem is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of $$\text {M-LWE}$$ , i.e., uniform secret modulo q and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress toward narrowing this gap. More precisely, we prove that $$\text {M-LWE}$$ with uniform $$\eta $$ -bounded secret for any $$1 \le \eta \ll q$$ and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of $$\text {M-LWE}$$ , provided that the module rank d is at least logarithmic in the ring degree n. We also prove that the search version of $$\text {M-LWE}$$ with large uniform secret and uniform $$\eta $$ -bounded error is at least as hard as the standard $$\text {M-LWE}$$ problem, if the number of samples m is close to the module rank d and with further restrictions on $$\eta $$ . The latter result can be extended to provide the hardness of search $$\text {M-LWE}$$ with uniform $$\eta $$ -bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.

DOI
10.1007/s00145-022-09441-3

Related papers

Hardness of decision (R)LWE for any modulus.

Adeline Roux-Langlois, Damien Stehlé

Abstract. The decision Learning With Errors problem has proven an extremely flexible foundation for devising provably secure cryptographic primitives. LWE can be expressed in terms of linear algebra over Z/qZ. This modulus q is the subject of study of the present work. When q is prime and small, or when it is exponential and composite with small factors, LWE is known to be at least as hard as standard worst-case problems over euclidean lattices (sometimes using quantum reductions). The Ring Learning With Errors problem is a structured variant of LWE allowing for more compact keys and more efficient primitives. It is known to be at least as hard as standard worst-case problems restricted to so-called ideal lattices, but under even more restrictive arithmetic conditions on q. In this work, we prove that the arithmetic form of the modulus q is irrelevant to the computational hardness of LWE and RLWE. More precisely, we show that these problems are at least as hard as standard worst-case problems on lattices, under the unique condition that q is of polynomial bit-size. This result is most useful for adapting LWE-based cryptographic constructions to the RLWE setting. Among others, this allows us to derive the first Identity-Based Encryption scheme of quasi-optimal performance proven secure under standard worst-case lattice assumptions, in the standard model. Other applications include authentication, functional encryption and traitor tracing.

•Jan 1, 2012•12 citations

Hardness of (Semiuniform) MLWE with Short Distributions Using the Rényi Divergence

Wenjuan Jia, Baocang Wang

The module learning with errors (MLWE) problem has attracted considerable attention for its tradeoff between security and efficiency. The quantum/classical worst‐case to average‐case hardness for the MLWE problem (or more exactly, a family of problems) has been established, but most of the known results require the seed distribution to be the uniform distribution. In the present paper, we show that, using the noise flooding technique based on the Rényi divergence, the search MLWE problem with uniform B ‐bounded secret distribution for 1 ≤ B ≪ q can still be hard for some seed distributions that are not (even computationally indistinguishable from) the uniform distribution under the standard MLWE assumption. Specifically, we show that if the seed distribution is a semiuniform distribution (namely, the seed distribution can be publicly derived from and has a “small difference” to the uniform distribution), then for suitable parameter choices, the search MLWE problem with uniform bounded secret distribution is hard under the standard MLWE assumption. Moreover, we also show that under the appropriate setting of parameters, the search MLWE problem with uniform bounded noise distribution is at least as hard as the standard MLWE assumption using a different approach than the one used by Boudgoust et al. in [JoC 2023].

IET Information Security•Jan 1, 2023•0 citations

Worst-Case to Average-Case Reductions for Module Lattices.

Adeline Roux-Langlois, Damien Stehlé

Abstract. Most lattice-based cryptographic schemes are built upon the assumed hardness of the Short Integer Solution (SIS) and Learning With Errors (LWE) problems. Their efficiencies can be drastically improved by switching the hardness assumptions to the more compact Ring-SIS and Ring-LWE problems. However, this change of hardness assumptions comes along with a possible security weakening: SIS and LWE are known to be at least as hard as standard (worst-case) problems on euclidean lattices, whereas Ring-SIS and Ring-LWE are only known to be as hard as their restrictions to special classes of ideal lattices, corresponding to ideals of some polynomial rings. In this work, we define the Module-SIS and Module-LWE problems, which bridge SIS with Ring-SIS, and LWE with Ring-LWE, respectively. We prove that these average-case problems are at least as hard as standard lattice problems restricted to module lattices (which themselves generalize arbitrary and ideal lattices). As these new problems enlarge the toolbox of the lattice-based cryptographer, they could prove useful for designing new schemes. Importantly, the worst-case to average-case reductions for the module problems are (qualitatively) sharp, in the sense that there exist converse reductions. This property is not known to hold in the context of Ring-SIS/Ring-LWE: Ideal lattice problems could reveal easy without impacting the hardness of Ring-SIS/Ring-LWE. 1

•Jan 1, 2012•8 citations

Hardness of Module‐LWE with Semiuniform Seeds from Module‐NTRU

Wenjuan Jia, Jiang Zhang, Baocang Wang

The module learning with errors (MLWE) problem has attracted significant attention and has been widely used in building a multitude of lattice‐based cryptographic primitives. The hardness of the MLWE problem has been established for several variants, but most of the known results require the seed distribution (i.e., the distribution of matrix A ) to be the uniform distribution. In this paper, we show that under the Module‐N‐th degree Truncated polynomial Ring Units (NTRU) (MNTRU) assumption, the search MLWE problem can still be hard for some distributions that are not (even computationally indistinguishable from) the uniform distribution. Specifically, we show that if the seed distribution is a semiuniform distribution (namely, the seed distribution can be publicly derived from and has a “small difference” to the uniform distribution), then for appropriate settings of parameters, the search MLWE problem is hard under the MNTRU assumption. Moreover, we also show that under the appropriate settings of parameters, the search learning with errors over rings problem with semiuniform seeds can still be hard under the NTRU assumption due to our results for the search MLWE problem with semiuniform seeds being rank‐preserving.

IET Information Security•Jan 1, 2023•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

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
The Module Learning With Errors ( M-LWE\text {M-LWE}M-LWE ) problem is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of M-LWE\text {M-LWE}M-LWE , i.e., uniform secret modulo q and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress toward narrowing this gap. More precisely, we prove that M-LWE\text {M-LWE}M-LWE with uniform η\eta η -bounded secret for any 1≤η≪q1 \le \eta \ll q1≤η≪q and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of M-LWE\text {M-LWE}M-LWE , provided that the module rank d is at least logarithmic in the ring degree n. We also prove that the search version of M-LWE\text {M-LWE}M-LWE with large uniform secret and uniform η\eta η -bounded error is at least as hard as the standard M-LWE\text {M-LWE}M-LWE problem, if the number of samples m is close to the module rank d and with further restrictions on η\eta η . The latter result can be extended to provide the hardness of search M-LWE\text {M-LWE}M-LWE with uniform η\eta η -bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.
Abstract. The decision Learning With Errors problem has proven an extremely flexible foundation for devising provably secure cryptographic primitives. LWE can be expressed in terms of linear algebra over Z/qZ. This modulus q is the subject of study of the present work. When q is prime and small, or when it is exponential and composite with small factors, LWE is known to be at least as hard as standard worst-case problems over euclidean lattices (sometimes using quantum reductions). The Ring Learning With Errors problem is a structured variant of LWE allowing for more compact keys and more efficient primitives. It is known to be at least as hard as standard worst-case problems restricted to so-called ideal lattices, but under even more restrictive arithmetic conditions on q. In this work, we prove that the arithmetic form of the modulus q is irrelevant to the computational hardness of LWE and RLWE. More precisely, we show that these problems are at least as hard as standard worst-case problems on lattices, under the unique condition that q is of polynomial bit-size. This result is most useful for adapting LWE-based cryptographic constructions to the RLWE setting. Among others, this allows us to derive the first Identity-Based Encryption scheme of quasi-optimal performance proven secure under standard worst-case lattice assumptions, in the standard model. Other applications include authentication, functional encryption and traitor tracing.
The module learning with errors (MLWE) problem has attracted considerable attention for its tradeoff between security and efficiency. The quantum/classical worst‐case to average‐case hardness for the MLWE problem (or more exactly, a family of problems) has been established, but most of the known results require the seed distribution to be the uniform distribution. In the present paper, we show that, using the noise flooding technique based on the Rényi divergence, the search MLWE problem with uniform B ‐bounded secret distribution for 1 ≤ B ≪ q can still be hard for some seed distributions that are not (even computationally indistinguishable from) the uniform distribution under the standard MLWE assumption. Specifically, we show that if the seed distribution is a semiuniform distribution (namely, the seed distribution can be publicly derived from and has a “small difference” to the uniform distribution), then for suitable parameter choices, the search MLWE problem with uniform bounded secret distribution is hard under the standard MLWE assumption. Moreover, we also show that under the appropriate setting of parameters, the search MLWE problem with uniform bounded noise distribution is at least as hard as the standard MLWE assumption using a different approach than the one used by Boudgoust et al. in [JoC 2023].
Abstract. Most lattice-based cryptographic schemes are built upon the assumed hardness of the Short Integer Solution (SIS) and Learning With Errors (LWE) problems. Their efficiencies can be drastically improved by switching the hardness assumptions to the more compact Ring-SIS and Ring-LWE problems. However, this change of hardness assumptions comes along with a possible security weakening: SIS and LWE are known to be at least as hard as standard (worst-case) problems on euclidean lattices, whereas Ring-SIS and Ring-LWE are only known to be as hard as their restrictions to special classes of ideal lattices, corresponding to ideals of some polynomial rings. In this work, we define the Module-SIS and Module-LWE problems, which bridge SIS with Ring-SIS, and LWE with Ring-LWE, respectively. We prove that these average-case problems are at least as hard as standard lattice problems restricted to module lattices (which themselves generalize arbitrary and ideal lattices). As these new problems enlarge the toolbox of the lattice-based cryptographer, they could prove useful for designing new schemes. Importantly, the worst-case to average-case reductions for the module problems are (qualitatively) sharp, in the sense that there exist converse reductions. This property is not known to hold in the context of Ring-SIS/Ring-LWE: Ideal lattice problems could reveal easy without impacting the hardness of Ring-SIS/Ring-LWE. 1
The module learning with errors (MLWE) problem has attracted significant attention and has been widely used in building a multitude of lattice‐based cryptographic primitives. The hardness of the MLWE problem has been established for several variants, but most of the known results require the seed distribution (i.e., the distribution of matrix A ) to be the uniform distribution. In this paper, we show that under the Module‐N‐th degree Truncated polynomial Ring Units (NTRU) (MNTRU) assumption, the search MLWE problem can still be hard for some distributions that are not (even computationally indistinguishable from) the uniform distribution. Specifically, we show that if the seed distribution is a semiuniform distribution (namely, the seed distribution can be publicly derived from and has a “small difference” to the uniform distribution), then for appropriate settings of parameters, the search MLWE problem is hard under the MNTRU assumption. Moreover, we also show that under the appropriate settings of parameters, the search learning with errors over rings problem with semiuniform seeds can still be hard under the NTRU assumption due to our results for the search MLWE problem with semiuniform seeds being rank‐preserving.
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.
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.