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•3 citations

Smoothening Functions and the Homomorphism Learning Problem

Ruiz Lopez, A Luis

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.

•Sep 2, 2020•0 citations

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

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.
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.
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.
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.