4 results sorted by ID
Possible spell-corrected query: lan
Post-Quantum Fully Homomorphic Encryption with Group Ring Homomorphisms
Christopher Leonardi, Maya Gusak
Attacks and cryptanalysis
Gentry's groundbreaking work showed that a fully homomorphic, provably secure scheme is possible via bootstrapping a somewhat homomorphic scheme. However, a major drawback of bootstrapping is its high computational cost. One alternative is to use a different metric for noise so that homomorphic operations do not accumulate noise, eliminating the need for boostrapping altogether. Leonardi and Ruiz-Lopez present a group-theoretic framework for such a ``noise non-accumulating'' multiplicative...
On homomorphic encryption using abelian groups: Classical security analysis
Eleni Agathocleous, Vishnupriya Anupindi, Annette Bachmayr, Chloe Martindale, Rahinatou Yuh Njah Nchiwo, Mima Stanojkovski
Attacks and cryptanalysis
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 $\textit{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...
Hardness of Learning Problems over Burnside Groups of Exponent 3
Nelly Fazio, Kevin Iga, Antonio Nicolosi, Ludovic Perret, William E. Skeith III
Foundations
In this work we investigate the hardness of a computational problem introduced in the recent work of Baumslag et al. In particular, we study the $B_n$-LHN problem, which is a generalized version of the learning with errors (LWE) problem, instantiated with a particular family of non-abelian groups (free Burnside groups of exponent 3). In our main result, we demonstrate a random self-reducibility property for $B_n$-LHN. Along the way, we also prove a sequence of lemmas regarding homomorphisms...
Generalized Learning Problems and Applications to Non-Commutative Cryptography
Gilbert Baumslag, Nelly Fazio, Antonio R. Nicolosi, Vladimir Shpilrain, William E. Skeith III
Foundations
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 from 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...
Gentry's groundbreaking work showed that a fully homomorphic, provably secure scheme is possible via bootstrapping a somewhat homomorphic scheme. However, a major drawback of bootstrapping is its high computational cost. One alternative is to use a different metric for noise so that homomorphic operations do not accumulate noise, eliminating the need for boostrapping altogether. Leonardi and Ruiz-Lopez present a group-theoretic framework for such a ``noise non-accumulating'' multiplicative...
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 $\textit{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...
In this work we investigate the hardness of a computational problem introduced in the recent work of Baumslag et al. In particular, we study the $B_n$-LHN problem, which is a generalized version of the learning with errors (LWE) problem, instantiated with a particular family of non-abelian groups (free Burnside groups of exponent 3). In our main result, we demonstrate a random self-reducibility property for $B_n$-LHN. Along the way, we also prove a sequence of lemmas regarding homomorphisms...
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 from 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...