Generalized Learning Problems and Applications to Non-Commutative Cryptography

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

Paper 2011/357

Generalized Learning Problems and Applications to Non-Commutative Cryptography

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

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: Published elsewhere. Unknown where it was published
Keywords: Learning with errors Post-quantum cryptography Non-commutative cryptography Burnside groups.
Contact author(s): fazio @ cs ccny cuny edu
History: 2011-07-04: received
Short URL: https://ia.cr/2011/357
License: CC BY

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},
      note = {\url{https://eprint.iacr.org/2011/357}},
      url = {https://eprint.iacr.org/2011/357}
}