Hardness of learning problems over Burnside groups of exponent 3

Nelly Fazio, Kevin Iga, Antonio R. Nicolosi, Ludovic Perret, William E. Skeith

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

In this work, we investigate the hardness of learning Burnside homomorphisms with noise ((Formula presented.)LHN(Formula presented.)), a computational problem introduced in the recent work of Baumslag et al. This is a generalization of the learning with errors problem, instantiated with a particular family of non-abelian groups, known as free Burnside groups of exponent 3. In our main result, we demonstrate a random self-reducibility property for (Formula presented.)LHN(Formula presented.). Along the way, we also prove a sequence of lemmas regarding homomorphisms of free Burnside groups of exponent 3 that may be of independent interest.

Original languageEnglish
Pages (from-to)59-70
Number of pages12
JournalDesigns, Codes, and Cryptography
Volume75
Issue number1
DOIs
StatePublished - Apr 2015

Keywords

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

Fingerprint

Dive into the research topics of 'Hardness of learning problems over Burnside groups of exponent 3'. Together they form a unique fingerprint.

Cite this