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

Smoothening Functions and the Homomorphism Learning Problem

Ruiz Lopez, A Luis

Published Sep 2, 2020• 0 citations
OpenAlex

Abstract

This thesis is an exploration of certain algebraic and geometrical aspects of the Learning With Errors (LWE) problem introduced in Reg05. \n\tOn the algebraic front, we view it as a Learning Homomorphisms with Noise problem, and provide a generic construction of a public-key cryptosystem based on this generalization. \n\tOn the geometric front, we explore the importance of the Gaussian distribution for the existing relationships between LWE and lattice problems. \n\tWe prove that their smoothing properties does not make them special, but rather, the fact that it is infinitely divisible and l2 symmetric are important properties that make the Gaussian unique.

Related papers

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

On Ideal Lattices and Learning with Errors over Rings

Vadim Lyubashevsky, Chris Peikert, Oded Regev

The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called ring-LWE , and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.

Journal of the ACM•Nov 1, 2013•911 citations

Generalized Learning Problems and Applications to Non-Commutative Cryptography.

Gilbert Baumslag, Nelly Fazio, Antonio R. Nicolosi +2 more

Abstract. We propose a generalization of the learning parity with noise (LPN) and learning with errors (LWE) problems to an abstract class of group-theoretic learning problems that we term learning homomorphisms with noise (LHN). This class of problems contains LPN and LWE as special cases, but is much more general. It allows, for example, instantiations based on non-abelian groups, resulting in a new avenue for the application of combinatorial group theory to the development of cryptographic primitives. We then study a particular instantiation using relatively free groups and construct a symmetric cryptosystem based upon it. Keywords. Learning with errors. Post-quantum cryptography. Non-commutative cryptography. Burnside groups. 1

•Jan 1, 2011•0 citations

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

On lattices, learning with errors, random linear codes, and cryptography

Oded Regev

Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the 'learning from parity with error' problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for SVP and SIVP. A main open question is whether this reduction can be made classical.Using the main result, we obtain a public-key cryptosystem whose hardness is based on the worst-case quantum hardness of SVP and SIVP. Previous lattice-based public-key cryptosystems such as the one by Ajtai and Dwork were only based on unique-SVP, a special case of SVP. The new cryptosystem is much more efficient than previous cryptosystems: the public key is of size Õ(n2) and encrypting a message increases its size by Õ(n)(in previous cryptosystems these values are Õ(n4) and Õ(n2), respectively). In fact, under the assumption that all parties share a random bit string of length Õ(n2), the size of the public key can be reduced to Õ(n).

ACM Symposium on Theory of Computing (STOC)•May 22, 2005•2,530 citations

A Multi-Bit Fully Homomorphic Encryption With Shorter Public Key From LWE

Xinxia Song, Zhigang Chen, Liang Chen

There has been a great deal of work on improving the efficiency of fully homomorphic encryption (FHE) scheme. Our approach, in this regard, is to use the idea of packed ciphertexts to construct a multi-bit FHE with a short public key on the basis of the learning with errors (LWE) problem. More specifically, our FHE scheme builds on a basic encryption scheme that chooses LWE samples from the Gaussian distribution and adds Gaussian error to it. This results in decreasing the number of LWE samples from 2nlogq to n + 1. We prove that our FHE scheme is pragmatically feasible and its security relies on the hardness of the LWE problem. In addition, we form a new process of key switching for multi-bit FHE based on the ideas adopted by Brakerski et al. for optimizing the process of key switching. Finally, we analyze and compare the concrete parameters between our FHE scheme and BGH13 scheme. The result shows that compared with the BGH13 scheme, our scheme has a smaller public key by a factor about logq.

IEEE Access•Jan 1, 2019•11 citations
This thesis is an exploration of certain algebraic and geometrical aspects of the Learning With Errors (LWE) problem introduced in Reg05. \n\tOn the algebraic front, we view it as a Learning Homomorphisms with Noise problem, and provide a generic construction of a public-key cryptosystem based on this generalization. \n\tOn the geometric front, we explore the importance of the Gaussian distribution for the existing relationships between LWE and lattice problems. \n\tWe prove that their smoothing properties does not make them special, but rather, the fact that it is infinitely divisible and l2 symmetric are important properties that make the Gaussian unique.
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.
The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called ring-LWE , and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.
Abstract. We propose a generalization of the learning parity with noise (LPN) and learning with errors (LWE) problems to an abstract class of group-theoretic learning problems that we term learning homomorphisms with noise (LHN). This class of problems contains LPN and LWE as special cases, but is much more general. It allows, for example, instantiations based on non-abelian groups, resulting in a new avenue for the application of combinatorial group theory to the development of cryptographic primitives. We then study a particular instantiation using relatively free groups and construct a symmetric cryptosystem based upon it. Keywords. Learning with errors. Post-quantum cryptography. Non-commutative cryptography. Burnside groups. 1
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.
Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the 'learning from parity with error' problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for SVP and SIVP. A main open question is whether this reduction can be made classical.Using the main result, we obtain a public-key cryptosystem whose hardness is based on the worst-case quantum hardness of SVP and SIVP. Previous lattice-based public-key cryptosystems such as the one by Ajtai and Dwork were only based on unique-SVP, a special case of SVP. The new cryptosystem is much more efficient than previous cryptosystems: the public key is of size Õ(n2) and encrypting a message increases its size by Õ(n)(in previous cryptosystems these values are Õ(n4) and Õ(n2), respectively). In fact, under the assumption that all parties share a random bit string of length Õ(n2), the size of the public key can be reduced to Õ(n).
There has been a great deal of work on improving the efficiency of fully homomorphic encryption (FHE) scheme. Our approach, in this regard, is to use the idea of packed ciphertexts to construct a multi-bit FHE with a short public key on the basis of the learning with errors (LWE) problem. More specifically, our FHE scheme builds on a basic encryption scheme that chooses LWE samples from the Gaussian distribution and adds Gaussian error to it. This results in decreasing the number of LWE samples from 2nlogq to n + 1. We prove that our FHE scheme is pragmatically feasible and its security relies on the hardness of the LWE problem. In addition, we form a new process of key switching for multi-bit FHE based on the ideas adopted by Brakerski et al. for optimizing the process of key switching. Finally, we analyze and compare the concrete parameters between our FHE scheme and BGH13 scheme. The result shows that compared with the BGH13 scheme, our scheme has a smaller public key by a factor about logq.