Paper 2011/398

Hardness of Learning Problems over Burnside Groups of Exponent 3

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

Abstract

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 of free Burnside groups of exponent 3 that may be of independent interest.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Random self-reducibilityLearning with errorsPost-quantum cryptographyNon-commutative cryptographyBurnside groups.
Contact author(s)
wes @ cs ccny cuny edu
History
2012-05-19: last of 3 revisions
2011-07-28: received
See all versions
Short URL
https://ia.cr/2011/398
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/398,
      author = {Nelly Fazio and Kevin Iga and Antonio Nicolosi and Ludovic Perret and William E.  Skeith III},
      title = {Hardness of Learning Problems over Burnside Groups of Exponent 3},
      howpublished = {Cryptology ePrint Archive, Paper 2011/398},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/398}},
      url = {https://eprint.iacr.org/2011/398}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.