Generalized learning problems and applications to non-commutative cryptography (Extended abstract)

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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

Original languageEnglish
Title of host publicationProvable Security - 5th International Conference, ProvSec 2011, Proceedings
Pages324-339
Number of pages16
DOIs
StatePublished - 2011
Event5th International Conference on Provable Security, ProvSec 2011 - Xi'an, China
Duration: 16 Oct 201118 Oct 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6980 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Conference on Provable Security, ProvSec 2011
Country/TerritoryChina
CityXi'an
Period16/10/1118/10/11

Keywords

  • Burnside groups
  • Learning with errors
  • Non-commutative cryptography
  • Post-quantum cryptography

Fingerprint

Dive into the research topics of 'Generalized learning problems and applications to non-commutative cryptography (Extended abstract)'. Together they form a unique fingerprint.

Cite this