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

Generalized Learning Problems and Applications to Non-Commutative Cryptography.

Gilbert Baumslag, Nelly Fazio, Antonio R. Nicolosi, Vladimir Shpilrain, William E. Skeith

Published Jan 1, 2011• 0 citations
OpenAlex

Abstract

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

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

Analysis of learning with errors problems with variational quantum algorithms

Jinfeng Zeng, Muxi Zheng, Hang Li +2 more

Abstract Variational Quantum Algorithms (VQAs) offer a promising approach to solving optimization problems on quantum computers. In this paper, we investigate the use of VQAs to solve the Learning With Errors (LWE) problem, a crucial challenge in post-quantum cryptography. We propose a VQA-based algorithm and a Quantum Approximate Optimization Algorithm (QAOA) for solving the Learning Parity with Noise (LPN) problem, a special case of LWE. We examine the sample complexity of combinatorial optimization methods for LPN and analyze the performance of these two variational quantum algorithms in terms of quantum resources. For the VQA algorithm, both the number of qubits and the circuit depth scale polynomially with the secret key length n . In the case of QAOA, the number of qubits matches the secret key length n , but the CNOT gate count increases exponentially with n . However, numerical simulations of the VQA-based algorithm show that choosing optimal ansatzes and optimization methods can significantly enhance success rates.

Europhysics Letters (EPL)•May 15, 2025•1 citation

Cryptography from hard learning problems

Daniel Masny

Der Umfang dieser Arbeit sind kryptographische Anwendungen von Lernproblemen zu welchen Learning Parity with Noise (LPN), Learning with Errors (LWE) und Learning with Rounding (LWR) zählen. Es hat sich herausgestellt, dass LPN eine wichtige Rolle in der Lern Theorie spielt. Aus Sicht der Kryptographie spielen LPN, LWE und LWR eine bedeutende Rolle. Nach aktuellen Wissen sind sie dazu in der Lage zahlreiche kryptographische Primitiven zu realisieren, sodass ihre Sicherheit auch in der Gegenwart von Quantencomputern gewährleistet ist. In dieser Arbeit wird aufgezeigt, dass LWR mindestens so schwer ist wie LWE. Es werden Protokolle für sichere Benutzer und Nachrichtenauthentifizierung vorgestellt, deren Sicherheit auf Pseudo-Zufalls Funktionen oder nicht-deterministische Varianten basiert, und es werden Chosen-Chiphertext sichere Public-Key-Verschlüsselung basierend auf Subset-Sum oder LPN konstruiert.

•Sep 5, 2016•0 citations

On the Hardness of the Asymmetric Learning With Errors Problem

Jiang Zhang, Shuqin Fan

Due to the advantages such as the worst-case hardness assumption, lattice-based cryptography is believed to the most promising research direction in post-quantum cryptography. As one of the two main hard problems commonly used in lattice-based cryptography, Learning With Errors (LWE) problem is widely used in constructing numerous cryptosystems. In order to improve the efficiency of lattice-based cryptosystems, Zhang et al. (2019) introduced the Asymmetric LWE (ALWE) problem. In this paper, the relation between the ALWE problem and the standard LWE problem is studied, and it shows that for certain error distributions the two problems are polynomially equivent, which paves the way for constructing secure lattice-based cryptosystems from the ALWE problem.

JOURNAL OF ELECTRONICS INFORMATION TECHNOLOGY•Feb 19, 2020•0 citations

Multiplicative Learning with Errors and Cryptosystems

Chunsheng Gu

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.

•Jan 7, 2014•1 citation

On homomorphic encryption using abelian groups: Classical security analysis

Eleni Agathocleous, Vishnupriya Anupindi, Annette Bachmayr +3 more

In [15], Leonardi and Ruiz-Lopez propose an additively homomorphic public key encryption scheme whose security is expected to depend on the hardness of the learning homomorphism with noise problem (LHN). Choosing parameters for their primitive requires choosing three groups $G$, $H$, and $K$. In their paper, Leonardi and Ruiz-Lopez claim that, when $G$, $H$, and $K$ are abelian, then their public key cryptosystem is not quantum secure. In this paper, we study security for finite abelian groups $G$, $H$, and $K$ in the classical case. Moreover, we study quantum attacks on instantiations with solvable groups.

arXiv:2302.12867•Feb 24, 2023•0 citations
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
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.
Abstract Variational Quantum Algorithms (VQAs) offer a promising approach to solving optimization problems on quantum computers. In this paper, we investigate the use of VQAs to solve the Learning With Errors (LWE) problem, a crucial challenge in post-quantum cryptography. We propose a VQA-based algorithm and a Quantum Approximate Optimization Algorithm (QAOA) for solving the Learning Parity with Noise (LPN) problem, a special case of LWE. We examine the sample complexity of combinatorial optimization methods for LPN and analyze the performance of these two variational quantum algorithms in terms of quantum resources. For the VQA algorithm, both the number of qubits and the circuit depth scale polynomially with the secret key length n . In the case of QAOA, the number of qubits matches the secret key length n , but the CNOT gate count increases exponentially with n . However, numerical simulations of the VQA-based algorithm show that choosing optimal ansatzes and optimization methods can significantly enhance success rates.
Der Umfang dieser Arbeit sind kryptographische Anwendungen von Lernproblemen zu welchen Learning Parity with Noise (LPN), Learning with Errors (LWE) und Learning with Rounding (LWR) zählen. Es hat sich herausgestellt, dass LPN eine wichtige Rolle in der Lern Theorie spielt. Aus Sicht der Kryptographie spielen LPN, LWE und LWR eine bedeutende Rolle. Nach aktuellen Wissen sind sie dazu in der Lage zahlreiche kryptographische Primitiven zu realisieren, sodass ihre Sicherheit auch in der Gegenwart von Quantencomputern gewährleistet ist. In dieser Arbeit wird aufgezeigt, dass LWR mindestens so schwer ist wie LWE. Es werden Protokolle für sichere Benutzer und Nachrichtenauthentifizierung vorgestellt, deren Sicherheit auf Pseudo-Zufalls Funktionen oder nicht-deterministische Varianten basiert, und es werden Chosen-Chiphertext sichere Public-Key-Verschlüsselung basierend auf Subset-Sum oder LPN konstruiert.
Due to the advantages such as the worst-case hardness assumption, lattice-based cryptography is believed to the most promising research direction in post-quantum cryptography. As one of the two main hard problems commonly used in lattice-based cryptography, Learning With Errors (LWE) problem is widely used in constructing numerous cryptosystems. In order to improve the efficiency of lattice-based cryptosystems, Zhang et al. (2019) introduced the Asymmetric LWE (ALWE) problem. In this paper, the relation between the ALWE problem and the standard LWE problem is studied, and it shows that for certain error distributions the two problems are polynomially equivent, which paves the way for constructing secure lattice-based cryptosystems from the ALWE problem.
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.
In [15], Leonardi and Ruiz-Lopez propose an additively homomorphic public key encryption scheme whose security is expected to depend on the hardness of the learning homomorphism with noise problem (LHN). Choosing parameters for their primitive requires choosing three groups GGG, HHH, and KKK. In their paper, Leonardi and Ruiz-Lopez claim that, when GGG, HHH, and KKK are abelian, then their public key cryptosystem is not quantum secure. In this paper, we study security for finite abelian groups GGG, HHH, and KKK in the classical case. Moreover, we study quantum attacks on instantiations with solvable groups.