Paper 2011/357 Original: eprint.iacr.org/2011/357 ↗
Generalized Learning Problems and Applications to Non-Commutative Cryptography
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 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 primitives. We then study a particular instantiation using relatively free groups and construct a symmetric cryptosystem based upon it.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2011-07-04: last updated
- 2011-07-04: published
- Short URL
- https://ia.cr/2011/357
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2011/357,
author = {Gilbert Baumslag and Nelly Fazio and Antonio R. Nicolosi and Vladimir Shpilrain and William E. Skeith III},
title = {Generalized Learning Problems and Applications to Non-Commutative Cryptography},
howpublished = {Cryptology {ePrint} Archive, Paper 2011/357},
year = {2011},
url = {https://eprint.iacr.org/2011/357}
}