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

Multiplicative Learning with Errors and Cryptosystems

Chunsheng Gu

Published Jan 7, 2014• 1 citation
OpenAlex

Abstract

Abstract: We introduce a new concept, called multiplicative learning with errors (MLWE), which is a corresponding multiplicative version of the additive learning with errors (LWE), and show the equivalence between the decisional version and the search version for MLWE such that p is a product of sufficiently large smoothing prime factors. Then we construct the MLWE-based private-key and public-key encryption schemes, whose securities are based on the worst-case hardness assumption of the MLWE problem. Finally, we discuss how to extend the LWE on additive group to the LWE on general abelian group.

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

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

Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem

Chris Peikert

We construct public-key cryptosystems that are secure assuming the *worst-case* hardness of approximating the shortest vector problem on lattices. Prior cryptosystems with worst-case connections (e.g., the Ajtai-Dwork system) were based either on a *special case* of the shortest vector problem, or on the conjectured hardness of lattice problems for *quantum* algorithms. Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on LWE, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-case approximation factor than prior constructions. (Duration: 30 minutes, on or before Wednesday.)

Dagstuhl Seminar Proceedings•Jan 1, 2009•192 citations

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

Securely Instantiating Cryptographic Schemes Based on the Learning with Errors Assumption

Florian Göpfert

Since its proposal by Regev in 2005, the Learning With Errors (LWE) problem was used as the underlying problem for a great variety of schemes. Its applications are many-fold, reaching from basic and highly practical primitives like key exchange, public-key encryption, and signature schemes to very advanced solutions like fully homomorphic encryption, group signatures, and identity based encryption. One of the underlying reasons for this fertility is the flexibility with that LWE can be instantiated. Unfortunately, this comes at a cost: It makes selecting parameters for cryptographic applications complicated. When selecting parameters for a new LWE-based primitive, a researcher has to take the influence of several parameters on the efficiency of the scheme and the runtime of a variety of attacks into consideration. In fact, the missing trust in the concrete hardness of LWE is one of the main problems to overcome to bring LWE-based schemes to practice. This thesis aims at closing the gap between the theoretical knowledge of the hardness of LWE, and the concrete problem of selecting parameters for an LWE-based scheme. To this end, we analyze the existing methods to estimate the hardness of LWE, and introduce new estimation techniques where necessary. Afterwards, we show how to transfer this knowledge into instantiations that are at the same time secure and efficient. We show this process on three examples: - A highly optimized public-key encryption scheme for embedded devices that is based on a variant of Ring-LWE. - A practical signature scheme that served as the foundation of one of the best lattice-based signature schemes based on standard lattices. - An advanced public-key encryption scheme that enjoys the unique property of natural double hardness based on LWE instances similar to those used for fully homomorphic encryption.

•Jan 1, 2016•2 citations

Public-Key Encryption Schemes with Auxiliary Inputs. Theory of Cryptography

Yevgeniy Dodis, Shafi Goldwasser

Abstract. We construct public-key cryptosystems that remain secure even when the adversary is given any computationally uninvertible function of the secret key as auxiliary input (even one that may reveal the secret key informationtheoretically). Our schemes are based on the decisional Diffie-Hellman (DDH) and the Learning with Errors (LWE) problems. As an independent technical contribution, we extend the Goldreich-Levin theorem to provide a hard-core (pseudorandom) value over large fields. 1

•Feb 1, 2010•1 citation
Abstract: We introduce a new concept, called multiplicative learning with errors (MLWE), which is a corresponding multiplicative version of the additive learning with errors (LWE), and show the equivalence between the decisional version and the search version for MLWE such that p is a product of sufficiently large smoothing prime factors. Then we construct the MLWE-based private-key and public-key encryption schemes, whose securities are based on the worst-case hardness assumption of the MLWE problem. Finally, we discuss how to extend the LWE on additive group to the LWE on general abelian group.
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 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.
We construct public-key cryptosystems that are secure assuming the *worst-case* hardness of approximating the shortest vector problem on lattices. Prior cryptosystems with worst-case connections (e.g., the Ajtai-Dwork system) were based either on a *special case* of the shortest vector problem, or on the conjectured hardness of lattice problems for *quantum* algorithms. Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on LWE, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-case approximation factor than prior constructions. (Duration: 30 minutes, on or before Wednesday.)
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.
Since its proposal by Regev in 2005, the Learning With Errors (LWE) problem was used as the underlying problem for a great variety of schemes. Its applications are many-fold, reaching from basic and highly practical primitives like key exchange, public-key encryption, and signature schemes to very advanced solutions like fully homomorphic encryption, group signatures, and identity based encryption. One of the underlying reasons for this fertility is the flexibility with that LWE can be instantiated. Unfortunately, this comes at a cost: It makes selecting parameters for cryptographic applications complicated. When selecting parameters for a new LWE-based primitive, a researcher has to take the influence of several parameters on the efficiency of the scheme and the runtime of a variety of attacks into consideration. In fact, the missing trust in the concrete hardness of LWE is one of the main problems to overcome to bring LWE-based schemes to practice. This thesis aims at closing the gap between the theoretical knowledge of the hardness of LWE, and the concrete problem of selecting parameters for an LWE-based scheme. To this end, we analyze the existing methods to estimate the hardness of LWE, and introduce new estimation techniques where necessary. Afterwards, we show how to transfer this knowledge into instantiations that are at the same time secure and efficient. We show this process on three examples: - A highly optimized public-key encryption scheme for embedded devices that is based on a variant of Ring-LWE. - A practical signature scheme that served as the foundation of one of the best lattice-based signature schemes based on standard lattices. - An advanced public-key encryption scheme that enjoys the unique property of natural double hardness based on LWE instances similar to those used for fully homomorphic encryption.